中国剩余定理

也叫”孙子定理”

中国剩余定理.pdf

例题

204. 表达整数的奇怪方式

给定 2n 个整数 a1,a2,…,an 和 m1,m2,…,mn，求一个最小的非负整数 x，满足 ∀i∈[1,n],x≡mi(mod ai)。
输入格式
第 1 行包含整数 n。
第 2…n+1行：每 i+1行包含两个整数 ai 和 mi，数之间用空格隔开。
输出格式
输出最小非负整数 x，如果 x 不存在，则输出 −1。
如果存在 x，则数据保证 x 一定在 64 位整数范围内。
数据范围
1≤ai≤231−1
0≤mi1≤n≤25
输入样例：

2
8 7
11 9

输出样例：

31

思路：
不是严格意思上的中国剩余定理，因为题目没有说任意 mi, mj 两两互质
所以可能有解，也可能无解，需要一步一步算
每次合并两个同余式并判断是否有解，有解则继续计算，否则退出计算
表达整式的奇怪方式.pdf

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long a1, m1;
        a1 = sc.nextLong();
        m1 = sc.nextLong();
        //解的标识
        boolean flag = true;
        long x = 0;
        for (int i = 0; i < n - 1; i++) {
            long a2, m2;
            a2 = sc.nextInt();
            m2 = sc.nextInt();
            long[] k1 = new long[1], k2 = new long[1];
            long d = exgcd(a1, a2, k1, k2);
            //是否有解的判断
            if ((m2 - m1) % d != 0) {
                flag = false;
                x = -1;
                break;
            }
            //有解
            long t = (m2 - m1) / d;
            //求系数解
            k1[0] *= t;
            //求系数的最小非负整数特解
            k1[0] = (k1[0] % (a2/d) + (a2/d)) % (a2/d);
            //求当前x的特解
            x = k1[0] * a1 + m1;
            //求x的通解系数，方便下一轮迭代
            m1 = x;
            a1 = Math.abs(a1 / d * a2);
        }
        System.out.println(x);
    }
    static long exgcd(long a, long b, long[] x, long[] y) {
        if (b == 0) {
            x[0] = 1;
            y[0] = 0;
            return a;
        }
        long d = exgcd(b, a % b, y, x);
        y[0] -= a / b * x[0];
        return d;
    }
}