C++ 编程：破解密码算法

近日来勒索病毒事件频繁发生，小 Y 对它的加密原理非常感兴趣，研究了一番相关知识之后，他就来给你看他的加密程序，并给你一段密文，和你炫耀说就算把程序给你看你也破解不出来。

你扫了一眼代码发现加密的公式为 b=ae%m，其中 e 是质数。

进一步分析发现 m=p*q，p 和 q 都为质数，p≠q，

作为一个计算机高手，你早就对加密算法烂熟于心，一眼就看出这个程序的算法和原理，找到了破解的方法，发现小 Y 疏忽在与给了你一个不够大的 m。

你知道解密的公式与加密对称，为 a=bd%m。

但是你仍然无法心算解出这个 d，因此你需要借助计算机来将密文破解。

输入

第一行有一个整数 T 表示数据组数。（T<=100）

接着有 T 组数据，每组数据两行。

第一行有四个数 e、p、q 和 n，其中 e、p、q 如题所描述，n 表示需要解密的数字序列长度。

第二行是需要解密的数字序列 a1..an。

1<p,q,e<=10^8，p、q、e 为质数且 p≠q 。

$0<=a_i 保证解密的结果即原数列的值小于 min(p,q) 并大于等于 0

1<=n<=100

保证 m 有且仅有两个不同的质因数 p 和 q，并且一定存在一个题中描述的参数 d 使得解密公式能够无损解密出所有 0~min(p,q)−1 范围之间的数字。

输出

对于每组数据输出一行，表示解密后的数字序列，数字之间以空格隔开。

样例输入 1

1 5 19 29 3 335 440 514

样例输出 1

65 67 77

提示

对于样例，存在 d=101 使得解密公式成立。

注意 m 和 ai 的大小可能超过 int 的范围

代码示例

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

long long mod_inverse(long long a, long long m) {
    long long m0 = m, t, q;
    long long x0 = 0, x1 = 1;

    if (m == 1)
        return 0;

    while (a > 1) {
        q = a / m;
        t = m;

        m = a % m;
        a = t;
        t = x0;

        x0 = x1 - q * x0;
        x1 = t;
    }

    if (x1 < 0)
        x1 += m0;

    return x1;
}

vector<long long> decrypt(int e, int p, int q, int n, vector<long long>& ciphertext) {
    long long m = p * q;
    long long phi = (p - 1) * (q - 1);
    long long d = mod_inverse(e, phi);
    vector<long long> plaintext(n);

    for (int i = 0; i < n; i++) {
        long long c = ciphertext[i];
        long long a = pow(c, d);
        plaintext[i] = a % m;
    }

    return plaintext;
}

int main() {
    int T;
    cin >> T;

    while (T--) {
        int e, p, q, n;
        cin >> e >> p >> q >> n;
        vector<long long> ciphertext(n);

        for (int i = 0; i < n; i++) {
            cin >> ciphertext[i];
        }

        vector<long long> plaintext = decrypt(e, p, q, n, ciphertext);

        for (int i = 0; i < n; i++) {
            cout << plaintext[i] << " ";
        }

        cout << endl;
    }

    return 0;
}

在以上代码中，我们首先定义了一个 mod_inverse 函数来计算模反元素 d。然后，我们定义了一个 decrypt 函数来进行解密操作。在函数中，我们首先计算 m 和 phi 的值，然后使用 mod_inverse 函数求解 d。接着，我们对每个密文进行解密，得到明文后返回结果。

在主程序中，我们首先读取输入的数据，然后调用 decrypt 函数进行解密，并将结果打印出来。

该代码使用了 long long 来处理可能超过 int 范围的情况，并使用了 pow 函数来计算幂次，需要包含头文件 <cmath>。

希望这个代码示例对你有帮助！如果有任何问题，请随时提问。