D 韩信点兵

性质: 给定整数 a 和 b , 对 a 加上 b 的任意倍数, a % b 的结果不变
=> 如果 x 满足约束 x % a = b , 则 x + ka 也满足约束
=> 方程 x % a = b, 特解 x = x0 的通解为 x = x0 + ka

令 x[i] 为满足前i个约束的解的最小值
X[i] 为满足前i个约束的解的通解
Lcm[i]=lcm(a[0],a[1],,...,a[i])

只考虑前i个约束的通解:
X[i] = x[i] + k1 * Lcm[i]

考虑第i+1个约束:
X[i+1] = x[i+1] + k2 * Lcm[i+1] = k3 * Lcm[i]

因为 X[i+1] ⊆ X[i] (满足前i+1个约束,一定满足前i个约束)

则可得到递推式:
① x[i+1] = x[i] + t*Lcm[i], 其中t从0开始枚举, 直到满足x[i+1] % a[i] == b[i]
② Lcm[i+1] = lcm( Lcm[i], a[i+1]) 

初值:
lcm初值为1
x初始值为0, (x=1 WA了1个, 别问我怎么知道的, 我调两天了)

如何判断无解:

现在有新的约束 (a[i], b[i]), 要用 x[i-1] 和 lcm[i-1] 求 x[i]

即找到一个(最小的)t, 使得 x[i] = x[i-1] + t * lcm[i-1]

(x + t * lcm) % a = b 
⇔ t * lcm = b - x (mod a)

这是一个同余方程, t有解的充要条件是 gcd(a,lcm)|(b-x)

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);

    static int I() {
        return sc.nextInt();
    }

    static long L() {
        return sc.nextLong();
    }

    public static void main(String[] args) {
        int n = I();
        BigInteger m = BigInteger.valueOf(L());
        //x[i]:满足前i个约束的最小x; lcm[i]:前i个约束的最小公倍数
        BigInteger x = BigInteger.ZERO, lcm = BigInteger.ONE;
        for (int i = 0; i < n; i++) {
            BigInteger a = BigInteger.valueOf(L()), b = BigInteger.valueOf(L());// 约束 ans % a = b
            // (x+t*lcm)%a=b => lcm * t = b-x (mod a)
            // 形如同余方程 ax = b ( mod p )
            // ax = b (mod p) 有解条件 gcd(a,p)|b
            // 即 (b-x) % gcd(lcm,a) = 0
            BigInteger gcd = lcm.gcd(a);
            if (!b.subtract(x).mod(gcd).equals(BigInteger.ZERO)) {// 无解
                System.out.println("he was definitely lying");
                return;
            }
            while (!x.mod(a).equals(b)) {
                x = x.add(lcm); // x[i+1] = x[i] + t*Lcm[i]
            }
            lcm = lcm.multiply(a).divide(gcd); // Lcm[i+1] = lcm( Lcm[i], a[i+1]) 
        }
        System.out.println(x.compareTo(m) > 0 ? "he was probably lying" : x);
    }
}