6-表达整数的奇怪方式

算法思想

算法模板

public class Main {
    static long k1, k2;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long a1 = in.nextInt();
        long m1 = in.nextInt();
        long x = 0;

        for(int i = 1; i < n; i ++)
        {
            long a2 = in.nextInt(),
                m2 = in.nextInt();
            long d = exgcd(a1, a2);
            if((m2 - m1) % d != 0)
            {
                x = -1;
                break;
            }

            // 求解出 k1 的特解
            k1 *= (m2 - m1) / d;
            // k1 通解的通项
            long general = a2 / d;
            k1 = (k1 % general + general) % general;

            // 合并两个公式为一个新的公式
            // 由 x = k1 * a1 + m1 和 k1 的通解，
            // 我们可以得出关于 x 的新的公式，
            // 至此完成了两个公式的合并
            m1 = m1 + a1 * k1;
            a1 = Math.abs(a1 / d * a2);
        }

        if(x != -1)
        {
            long general = a1;
            x = (m1 % general + general) % general;
        }

        System.out.println(x);
    }

    public static long exgcd(long a, long b)
    {
        if(b == 0)
        {
            k1 = 1; k2 = 0;
            return a;
        }
        long d = exgcd(b, a % b);
        long x1 = k1;
        long y1 = k2;
        k1 = y1;
        k2 = x1 - a / b * y1;

        return d;
    }
}

参考资料