思路梳理题解，不喜勿喷

基本思路

首先是推公式

先从两个式子推起。

$x ≡ m_1 (mod\ a_1)$

$x ≡ m_2 (mod\ a_2)$

可得

$x = k_1 × a_1 + m_1$

$x = k_2 × a_2 + m_2$

（$k_1$和$k_2$为一组符合要求的整数）

等量代换

$k_1 × a_1 + m_1 = k_2 × a_2 + m_2$

移项

$k_1 × a_1 - k_2 × a_2 = m_2 - m_1$

整理一下

$k_1 × a_1 + k_2 × (-a_2) = m_2 - m_1$

感觉是不是很像扩展欧几里得？

$k_1 × a_1 + k_2 × (-a_2) = gcd(a_1,-a_2)$

所以如果

$gcd(a_1,-a_2) ∤ m_2 - m_1$

那么就无解。

否则

可以通过扩展欧几里得算法求出$k_1$，$k_2$，满足

$k_1 × a_1 + k_2 × (-a_2) = gcd(a_1,-a_2)$

然后翻$( m_2 - m_1 ) ÷ gcd(a_1,-a_2)$倍，得到答案。

最小解

如果把

$k_1 + k\frac{a_2}{gcd(a_1,-a_2)}$

同时

$k_2 + k\frac{a_1}{gcd(a_1,-a_2)}$

（k为任意整数）

那么结果不会变。

这里暂时只考虑$k_1$

那么$k_1$的最小解就是

$k_1$ % $|\frac{a_2}{gcd(a_1,-a_2)}|$

（我们不知道$\frac{a_2}{gcd(a_1,-a_2)}$的正负）

证明

$(k_1 + k\frac{a_2}{gcd(a_1,-a_2)}) × a_1 + (k_2 + k\frac{a_1}{gcd(a_1,-a_2)}) × (-a_2)$

去括号

$k_1×a_1+k\frac{a_2×a_1}{gcd(a_1,-a_2)}+k_2×(-a_2)+k\frac{a_1×(-a_2)}{gcd(a_1,-a_2)}$

整理一下

$k_1×a_1+k\frac{a_2×a_1}{gcd(a_1,-a_2)}+k_2×(-a_2)-k\frac{a_1×a_2}{gcd(a_1,-a_2)}$

$k_1×a_1+k_2×(-a_2)$

和前面的式子完全等价

扩展到多个式子

大家应该还记得前面的

$x = k_1 × a_1 + m_1$

现在，我们可以把它换成

$x = (k_1+k\frac{a_2}{gcd(a_1,-a_2)}) × a_1 + m_1$

整理一下式子

$x = k_1 × a_1 + k\frac{a_2}{gcd(a_1,-a_2)} × a_1 + m_1$

$x = k\frac{a_2 × a_1}{gcd(a_1,-a_2)}+(k_1 × a_1 + m_1)$

是不是有些眼熟？

新的

$k_1 = k$

$a_1 = |\frac{a_2 × a_1}{gcd(a_1,-a_2)}|$（这里也不知道正负，所以加绝对值）

$m_1 = 原先的m_1+k_1 × a_1$

于是两个式子就被合并成了一个！

最终解法

把多个式子全合并起来

最后要求最小解

所以最小解就是

最终求出的$m_1$

（$k_1=0$）

C++ 代码

#include<iostream>
#include<cmath>
using namespace std;
typedef long long LL;   //题目的数据范围要开long long
LL exgcd(LL a,LL b,LL &x,LL &y){    //扩展欧几里得
    if(!b){
        x=1,y=0;
        return a;
    }
    int res=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return res;
}
int main(){
    int n;
    LL a1,m1;
    scanf("%d%lld%lld",&n,&a1,&m1);
    for(int i=1;i<n;i++){
        LL a2,m2,k1,k2;
        scanf("%lld%lld",&a2,&m2);
        LL d=exgcd(a1,-a2,k1,k2);
        if((m1-m2)%d){  //判断无解
            puts("-1");
            return 0;
        }
        k1*=(m2-m1)/d;  //翻倍
        k1=(k1%abs(a2/d)+abs(a2/d))%abs(a2/d);  //求最小
        m1+=k1*a1;
        a1=abs(a1/d*a2);    //为避免溢出，先除再乘
    }
    printf("%lld",m1);
    return 0;
}