java剩余定理的代码实现
时间: 2023-05-29 18:05:37 浏览: 50
以下是Java中剩余定理的代码实现:
```
public class ChineseRemainderTheorem {
// 计算最大公约数
public static long gcd(long a, long b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
// 计算最小公倍数
public static long lcm(long a, long b) {
return a * b / gcd(a, b);
}
// 求逆元
public static long modInverse(long a, long m) {
long m0 = m, t, q;
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;
}
// 求解同余方程组
public static long chineseRemainder(long[] num, long[] rem) {
int k = rem.length;
long prod = 1;
for (int i = 0; i < k; i++) {
prod *= num[i];
}
long result = 0;
for (int i = 0; i < k; i++) {
long pp = prod / num[i];
result += rem[i] * modInverse(pp, num[i]) * pp;
}
return result % prod;
}
public static void main(String[] args) {
long[] num = {3, 5, 7};
long[] rem = {2, 3, 2};
long x = chineseRemainder(num, rem);
System.out.println("x = " + x);
}
}
```
其中,`gcd`函数计算最大公约数,`lcm`函数计算最小公倍数,`modInverse`函数求逆元,`chineseRemainder`函数求解同余方程组,`main`函数为测试代码,输出结果为`x = 23`。