java---中国剩余定理---表达整数的奇怪方式（每日一道算法2022.9.19）

注意事项：
请确保你已理解并掌握：
java—最大公因数gcd—辗转相除法
java—扩展欧几里得算法(extend gcd)
java—扩展欧几里得—线性同余方程

题目：
给定 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 位整数范围内

输入:
2
8 7
11 9
1
2
3
4

输出：
31
1
2

public class 中国剩余定理_表达整数的奇怪方式 {
    public static long k1, k2;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        //这里设置一个变量判断答案是否存在
        boolean has_answer = true;
        //每次合并两个不定式，k1*a1 + m1 = k2*a2 + m2, 一共合并n-1次
        long a1 = in.nextInt(), m1 = in.nextInt();
        for (int i = 0; i < n-1; i++) {
            long a2 = in.nextInt(), m2 = in.nextInt();

            long d = ex_gcd(a1, a2);     //通过两个不定式找到d
            if ((m2-m1) % d != 0) {       //如果有解，那么m2-m1 % d一定等于0
                has_answer = false;
                break;
            }

            k1 *= (m2-m1)/d;              //这里和线性同余方程差不多，线性同余方程里是b，我们这里是m2-m1，都是d的倍数
            long t = a2 / d;                //拿到k的最小解，那么k就为1即可，不参与计算
            k1 = (k1 % t + t) % t;          //将k1变为最小正整数解

            m1 = a1 * k1 + m1;              //根据推导这里是x0
            a1 = Math.abs(a1 / d * a2);     //根据推导这里是ka
        }

        //这里是因为计算机中的%和数学意义上的%不太一样，计算机中的%是会得到负数的，那么我们通过(num1%num2+num2)%num2,就能得到数学意义上的%结果了
        if (has_answer) System.out.println((m1 % a1 + a1) % a1);
        else System.out.println("-1");
    }

    //还是扩展欧几里得算法，只不过我们把x和y替换为了k1和k2, 然后把所有变量的类型变为long即可，求出a和b的最小公因数
    public static long ex_gcd(long a, long b) {
        if (b == 0) {
            k1 = 1; k2 = 0; return a;
        }
        long d = ex_gcd(b, a%b);
        long temp = k1;
        k1 = k2;
        k2 = temp - a/b * k2;
        return d;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

推导过程：

我快死了我快死了我快死了！本来今天就脑壳痛，还整个这题
这就是初等数论吗，麻了！

声明：算法思路来源为y总，详细请见https://www.acwing.com/
本文仅用作学习记录和交流