原题链接

题意:

给定$2n$个整数$a_{1},a_{2},…,a_{n}$和$m_{1},m_{2},…,m_{n}$,求一个最小的非负整$x$，满足$∀i \in [1,n],x \equiv m_{i}(\mod a_{i})$

题解：

也就是求解方程组

$$\begin{cases} x \equiv m_{1} \mod a_{1}\\\ x \equiv m_{2} \mod a_{2}\\\ \cdots\cdots\\\ x \equiv m_{n} \mod a_{n}\\\ \end{cases} $$

因为中国剩余定理要求$a_{1},a_{2},…,a_{n}$两两互质，而此题并无该条件，故而只能自己推导求解方法

现在只看前两个方程
$$\begin{cases} x \equiv m_{1} \mod a_{1} \\\ x \equiv m_{2} \mod a_{2}\\\ \end{cases} $$
等价于
$$\begin{cases} x = a_{1}\*k_{1}+ m_{1} \quad k_{1} \in \mathbb{Z}\\\ x=a_{2}\*k_{2} + m_{2}\quad k_{2} \in \mathbb{Z}\\\ \end{cases} $$
即
$$a_{1}\*k_{1}+ m_{1} = a_{2}\*k_{2} + m_{2}$$
令 $k2 = -k2$ 整理可得:
$$a_{1}\*k_{1}+ a_{2}\*k_{2} = m_{2}-m_{1} $$
利用扩展欧几里得即可求得该方程的解$k_{1}$和$k_{2}$

设$k_{01},k_{02}$为方程 $a_{1}\*k_{01}+ a_{2}\*k_{02} = gcd(a_{1},a_{2})$的解

则当$gcd(a_{1},a_{2}) | m_{2}-m_{1}$时方程有解

此时的通解为
$$k_{1} =k_{01}\*(m_2-m_1)/gcd(a_{1},a_{2}) + k\*a_{2}/gcd(a_{1},a_{2})$$
$$k_{2} =k_{02}\*(m_2-m_1)/gcd(a_{1},a_{2}) - k\*a_{1}/gcd(a_{1},a_{2})$$
其中$k \in \mathbb{Z}$

为了防止计算过程中出现溢出，则需要在通解$k_{1}$中选出一个尽可能小的特解$k_{01}$，此处取为最小正整数特解

令$k_{01} = k_{01}\*(m_2-m_1)/gcd(a_{1},a_{2})$

则最小正整数特解为

$k_{01} = (\ k_{01}\%gcd(a_{1},a_{2})+a_{2}/gcd(a_{1},a_{2})\ )\%(a_{2}/gcd(a_{1},a_{2}))$

此时新的通解变为$k_{1} = k_{01}+k\*a_{2}/gcd(a_{1},a_{2})$

将求出的$k_{1}$带入方程
$$\begin{cases} x = a_{1}\*k_{1}+ m_{1}\\\ x=a_{2}\*k_{2} + m_{2}\\\ \end{cases}$$
则可知 $x = a_{1}\*k_{01}\*(m_2-m_1)/gcd(a_{1},a_{2}) + k\*a_{1}a_{2}/gcd(a_{1},a_{2})+m_{1}$
令
$a’=a_{1}a_{2}/gcd(a_{1},a_{2})=lcm(a_{1},a_{2})\ ,\ $
$m’ = a_{1}*k_{01} + m_{1}$

则原来两个方程转化为一个方程
$$x = a’\*k + m’$$
因此对于$n$个方程，采用此法，合并$n-1$次,即可化为一个方程$x = a’\*k + m’$
则此方程的最小正整数解即为$(m’\%a’+a’)\%a’$

C++代码如下

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL exgcd(LL a, LL b, LL &x, LL &y){//扩展欧几里得求ax+by=gcd(a,b)的解
    if(b==0){
        x = 1, y = 0;
        return a;
    }
    LL x1, y1, gcd = exgcd(b,a%b,x1,y1);
    x = y1, y = x1-a/b*y1;
    return gcd;
}
int main(){
    int n,has_ans=1;
    LL a1,m1,t;//第一个方程的系数 备份数据
    cin>>n;
    cin>>a1>>m1;//先输入第一个方程
    for(int i = 2,a2,m2; i <= n; i++){//合并接下来的n-1个方程
        cin>>a2>>m2;
        LL k01,k02,gcd = exgcd(a1,a2,k01,k02);
        if((m2-m1)%gcd){//此时无解
            has_ans = 0;
            break;
        }
        k01 = k01*(m2-m1)/gcd;//特解
        k01 = (k01 % (a2/gcd) + a2/gcd) % (a2/gcd);//让特解k01取到最小正整数解
        t = a1*a2/gcd;
        m1 += a1*k01;
        a1 = t;
    }
    if(has_ans) cout<<(m1%a1+a1)%a1<<endl;
    else cout<<-1<<endl;
    return 0;
}