PKU2891

[java]
package D0718;

/*
* 题目大体意思就是求x%ai=ri要求x的最小值
* 中国剩余定理
* 对于同余方程组：
* x=a1 (mod m1)
* x=a2 (mod m2)
* 方程组有一个小于m(m1,m2的最小公倍数）的非负整数解的充要条件是(a1-a2)%gcd(m1,m2)=0,同样利用扩展欧几里得算法。两式联立：a1+m1*y=a2+m2*z
* 则：a1-a2=m2*z-m1*y这样就可以解出z和y,则:x=a2+m2*z
* 而对于一般情形：(设m1,m2,...mk两两互素)时有：
* a=b[1] (mod w[1])
* a=b[2] (mod w[2])
* .....
* a=b[n] (mod w[n])
* 其中w,b已知，w[1],w[2]...w[n]是两两互素的正整数，求a
* 令W=w[1]*w[2]*...w[n]，用W[i]=W/w[i],因为gcd(W[i],w[i])=1,故有；两整数p[i],q[i]满足W[i]*p[i]+w[i]*q[i]=1;如果记e[i]=W[i]*p[i]，那么当j!=i时有:e[i]=0 (mod w[j]),当j=i时有：e[i]=1 (mod w[j]);
* 所以很明显：e[1]*b[1]+e2*b[2]+......e[k]*b[k]就是方程的一个解，加减W倍后就可以得到最小非负整数解了
* 而对于w[1],w[2].....w[n]不互素的情形，就只能两个两个来求了
* x=a[1] (mod m[1])
* x=a[2] (mod m[2])
* 解完后，a=x,m=m1和m2的最小公倍数
* 将题目意思转化为公式：a1*x-a2*y=r2-r1,用欧几里得扩展算法求解
* */
import java.util.Scanner;

public class PKU2891 {
    static boolean flag;
    static long d, x, y;
    static long result;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a1, m1, m2, a2, k;
        while (sc.hasNext()) {
            k = sc.nextLong();
            m1 = sc.nextLong();
            a1 = sc.nextLong();
            k -= 1;
            flag = false;
            result = 0;
            x = y = 0;
            d = 0;
            for (int i = 0; i < k; i++) {
                m2 = sc.nextLong();
                a2 = sc.nextLong();
                long b = a2 - a1;
                d = extend_GCD(m1, m2);
                if (b % d != 0)
                    flag = true;// 不存在整数解
                result = (x * (b / d) % m2 + m2) % m2;
                a1 = a1 + m1 * result; // 对于求多个方程
                m1 = (m1 * m2) / d; // lcm(m1,m2)最小公倍数；d是m1 和 m2 的最大公约数
                a1 = (a1 % m1 + m1) % m1;
            }
            if (flag)
                System.out.println(-1);
            else
                System.out.println(a1);
        }

    }

    // 扩展的欧几里德
    private static long extend_GCD(long a, long b) {
        long ret, t;
        if (b == 0) {
            x = 1;
            y = 0;
            return a;
        }
        ret = extend_GCD(b, a % b);
        t = x;
        x = y;
        y = t - (a / b) * y;
        return ret;
    }
}
作者：lhfight

补充：软件开发 , Java ,