C++ 解答中国剩余定理：代码实现及示例

中国剩余定理（Chinese Remainder Theorem）是一个求解一组同余方程的方法，假设给定一组同余方程：\n\n\tx \u2261 a1 (mod m1)\n\tx \u2261 a2 (mod m2)\n\t...\n\tx \u2261 an (mod mn)\n\n其中ai和mi分别为整数，mi之间互质。中国剩余定理可以求解出满足这组同余方程的x的唯一解。\n\n下面是用C++实现中国剩余定理的代码：\n\ncpp\n#include <iostream>\n#include <vector>\n#include <numeric>\nusing namespace std;\\n// 求解最大公约数\nint gcd(int a, int b) {\n if (b == 0) {\n return a;\n }\n return gcd(b, a % b);\n}\n\\n// 求解乘法逆元\nint modInverse(int a, int m) {\n int m0 = m;\n int y = 0, x = 1;\n\\n if (m == 1) {\n return 0;\n }\n\\n while (a > 1) {\n int q = a / m;\n int t = m;\n\\n m = a % m, a = t;\n t = y;\n\\n y = x - q * y;\n x = t;\n }\n\\n if (x < 0) {\n x += m0;\n }\n\\n return x;\n}\n\\n// 使用中国剩余定理求解同余方程组\nint chineseRemainderTheorem(const vector<int>& a, const vector<int>& m) {\n int M = accumulate(m.begin(), m.end(), 1, multiplies<int>());\n int x = 0;\n\\n for (int i = 0; i < m.size(); i++) {\n int Mi = M / m[i];\n x += a[i] * Mi * modInverse(Mi, m[i]);\n }\n\\n return x % M;\n}\n\\nint main() {\n // 示例：解同余方程组 x \u2261 2 (mod 3), x \u2261 3 (mod 5), x \u2261 2 (mod 7)\n vector<int> a = {2, 3, 2};\n vector<int> m = {3, 5, 7};\\n\\n int x = chineseRemainderTheorem(a, m);\n cout << "x = " << x << endl;\\n\\n return 0;\n}\n\n\n运行上述代码，输出结果为 x = 23，即满足给定同余方程组的唯一解为23。