中国剩余定理

public class Main {
    static BigInteger[] exgcd(BigInteger a, BigInteger b, BigInteger c) { // ax+by=c  res[0]=x,res[1]=y
        if (b.compareTo(BigInteger.ZERO) == 0) return new BigInteger[]{c.divide(a), BigInteger.ZERO};
        BigInteger[] r = exgcd(b, a.mod(b), c);
        return new BigInteger[]{r[1], r[0].subtract(a.divide(b).multiply(r[1]))};
    }

    static BigInteger[] merge(BigInteger x1, BigInteger p1, BigInteger x2, BigInteger p2) {
        BigInteger d = p1.gcd(p2);
        if (x2.subtract(x1).mod(d).compareTo(BigInteger.ZERO) != 0) return null;
        BigInteger[] r = exgcd(p1, p2, x2.subtract(x1));
        BigInteger p = p1.divide(d).multiply(p2); //     p=p1/d*p2
        BigInteger x=r[0].multiply(p1).add(x1).mod(p).add(p).mod(p);
        return new BigInteger[]{x, p};
    }
}