中国余数定理java
时间: 2023-10-11 17:18:11 浏览: 45
中国余数定理(CRT)是一种用于解决同余方程组的数学定理,它可以有效地降低计算量。下面是一个简单的Java实现:
```java
import java.util.Scanner;
public class CRT {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int[] a = new int[n];
int[] m = new int[n];
for (int i = 0; i < n; i++) {
a[i] = input.nextInt();
m[i] = input.nextInt();
}
System.out.println(crt(a, m));
}
private static int crt(int[] a, int[] m) {
int M = 1;
for (int i = 0; i < m.length; i++) {
M *= m[i];
}
int result = 0;
for (int i = 0; i < a.length; i++) {
int Mi = M / m[i];
int MiInverse = inverse(Mi, m[i]);
result += a[i] * Mi * MiInverse;
}
return result % M;
}
private static int inverse(int a, int b) {
int b0 = b, t, q;
int x0 = 0, x1 = 1;
if (b == 1) return 1;
while (a > 1) {
q = a / b;
t = b;
b = a % b;
a = t;
t = x0;
x0 = x1 - q * x0;
x1 = t;
}
if (x1 < 0) x1 += b0;
return x1;
}
}
```
在这个实现中,我们首先输入同余方程组的个数 n,然后依次输入每个方程的 a 和 m。crt 方法用于计算同余方程组的解,并返回最小非负整数解。inverse 方法用于计算一个数的逆元,也就是它在模意义下的倒数。