本文共 1955 字，大约阅读时间需要 6 分钟。

题目描述：

给定2n个整数a1,a2,…,an和m1,m2,…,mn,求一个最小的非负整数x，满足∀i∈[1,n],x≡mi(mod ai)。

输入格式

第1行包含整数n。第2..n行：每i+1行包含两个整数ai和mi,数之间用空格隔开。

输出格式

输出最小非负整数x，如果x不存在，则输出-1。如果存在x，则数据保证x一定在64位整数范围内。

数据范围

1≤ai≤2^31−1,0≤mi<ai,1≤n≤25

输入样例：

28 711 9

输出样例：

31

分析：

首先，介绍下中国剩余定理。中国剩余定理给出了以下的一元线性同余方程组：

有解的判定条件，并用给出了在有解情况下解的具体形式。中国剩余定理说明：假设m1,m2, ... ,mn，则对任意的整数：a1,a2, ... ,an，方程组S有解，并且通解可以用如下方式构造得到：设是整数m1,m2, ... ,mn的乘积，并设是除了mi以外的n- 1个整数的乘积。

设为Mi模mi的乘法逆元，

则方程组S的通解形式为  

在模M的意义下，方程组S只有一个解：

证明：

从假设可知，对任何，由于，所以

这说明存在整数ti使得（变换得tiMi + miy = 1，gcd（mi,MI）=1，故有解）。 也就是说正因为mi，mj互质，才保证了Mi模mi乘法逆元ti的存在。

对于aitiMi而言，又因为Mi是mj的倍数

所以满足：

即x就是方程组S的一个解。

另外，假设x1和x2都是S的解，则

而m1,m2,...,mn两两互质，故x1-x2被mi（i从1到n）整除，即整除x1 - x2.所以S的任意两个解之间必然相差M的整数倍，另一方面，是一个解，同时所有形式为：

的整数也是方程组S的解，所以方程组所有的解的集合就是：

对本题而言，要求x≡mi(mod ai)的最小非负整数解（注意这里ai和mi的含义与上面证明反过来了），由于没有ai,aj互质的条件，故不能保证乘法逆元的存在，所以需要重新求解。由x≡mi(mod ai)推出x = k1a1 + m1,x = k2a2 + m2。故k1a1 - k2a2 = m2 - m1，当gcd(a1,-a2) | m2 - m1时，前两个方程构成的方程组有解。同样，我们用扩展欧几里得算法来求解k1a1 - k2a2 = gcd(a1,-a2) = d的解后，乘上(m2 - m1) / d即可得到k1和k2真正的解。令k1=k1+k∗a2/d，k2=k2+k∗a1/d代入前面的方程发现依旧满足，所以我们得到了k1和k2的一组解，x = (k1+k*a2/d)a1 + m1=k1a1+m1+ka1a2/d=k1a1+m1+klcm(a1,a2)，令m = k1a1 + k2a2,a=lcm(a1,a2)就可以得到新的方程x=ka+m了，再与第三个方程继续这样求，直到剩下最后一个方程为止，此时，x=k1a1+m1，x取最小非负整数，则k1应该取k1 % (k*a2/d)，此时k1最小，x也最小。

#include 
   
    #include 
    
     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;    }    ll d = exgcd(b,a % b,y,x);    y -= a / b * x;    return d;}int main(){    int n;    cin>>n;    ll x = 0,m1,a1,m2,a2,k1,k2;    cin>>a1>>m1;    for(int i = 0;i < n - 1;i++){        cin>>a2>>m2;        ll d = exgcd(a1,-a2,k1,k2);        if((m2 - m1) % d){            x = -1;            break;        }        k1 *= (m2 - m1) / d;        k1 = (k1 % (a2 / d) + a2 / d) % (a2 / d);        x = k1 * a1 + m1;        ll a = abs(a1 / d * a2);        m1 = k1 * a1 + m1;        a1 = a;    }    if(x != -1) x = (x % a1 + a1) % a1;    cout<
     
      <
     
    
   

转载地址：https://blog.csdn.net/qq_30277239/article/details/103747201 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！