题目描述

思路：x≡m(mod a) -》 k1 * a1 - k2 * a2 = m1 - m2
1.通过扩展欧几里得算法把对应k11,k22求出来 k1 = k11 * (m2 - m1) *d
2.当k1，k2最小的时候，对应x1, x2 也最小，发现：
3.k1 = k1 + k * a2 / d; k2 = k2 + k * a1 / d(k取正整数)，因此k1, k2 有多组解， k = 0，k1最小。因此：
k1 = k1 % a2 / d ，由于不知道k1 是正是负，(x 要求最小非负整数)，所以 k1 = (k1 % a2 / d + a2 / d) % a2 / d 保证正数。
4.把 k1 + k * a2 / d 带入 x = k1 * a1 + m1 的 k1， 发现： x = k * lcm(a1, a2) + (k1 * a + m1) 符合通式
因此： a1 = lcm(a1, a2), m1 = (k1 * a + m1), x = k * a1 + m1 方程可以作为通式
最后答案就是当k = 0, x = m1

样例

2
8 7
11 9

算法1

(中国剩余定理)

参考文献

C++ 代码

#include<iostream>
using namespace std;
typedef long long LL;
LL exgcd(LL a, LL b, LL &x ,LL &y)
{
    if(!b)
    {
        x = 1, y = 0;
        return a;
    }
    else
    {
        LL t = exgcd(b, a % b, y, x);
        y -= a / b * x;
        return t;
    }
}

LL mmod(LL k, LL mod)
{
    return (k % mod + mod) % mod;
}
void resolution()
{
    int n;cin >> n;bool has_ans = true;
    LL a1,m1;cin >> a1 >> m1;
    while(--n)
    {
        LL a2, m2, k1, k2; cin >> a2 >> m2;
        LL d = exgcd(a1, a2, k1, k2);
        //cout << m1 - m2 <<endl;
        if((m1 - m2) % d)
        {
            has_ans = false;
            puts("-1");
            break;
        }
        k1 *= (m2 - m1) / d;
        /*k1=k1% abs(a2d)*/
        k1 = mmod(k1, a2 / d);//取到最小正整数
        /*合并两个方程*/
        LL a = (a1 * a2) / d;
        LL x = k1 * a1 + m1;
        m1 = x;
        a1 = a;
    }
    if(has_ans) cout << m1 << endl;
}

int main()
{
    resolution();
    return 0;
}