关键词：excrt

从题意我们可以简单地理解到这是中国剩余定理，那么我们就愉愉快快的把这个题交了上去

然后你AC了 想着双倍经验的你高高兴兴地拿去交 poj2891

发现只有40分

（黑人问号？？）

那么我们一起再回去学一次CRT（中国剩余定理）

当m1,m2,m3,m4,m5,……mn 两两互质的时候

x≡ai（mod mi）

我们得到的答案将会是

x = Σ ai * Mi * ti (i<=n)
Mi = m / mi (m为所有m的积）
ti 为 Mi * ti ≡ 1 （mod mi）的一个解

但是我们再回到这个题目 不互质！！！

所以可以用

数学归纳法！

对他就叫excrt

假设 前k-1的方程的通解是 x+i*m （m为前面所有%数的lcm）

要满足第k个方程 x+i*m ≡ ak（mod mk）

移项 i*m ≡ ak-x（mod mk）

如果可以求出 i x’=x+i*m 就是解 然后接着推

所以就是答案了！！

CRT：

#include<iostream>
#include<stdio.h>
#include<cmath>
#include<algorithm>
#include<string.h>
#define LL long long
using namespace std;
LL a[12],b[12],n,M=1;
inline LL exgcd(LL a,LL b,LL &x,LL &y)
{
    if(!b){
        x=1,y=0;
        return a;
    }
    LL d=exgcd(b,a%b,x,y);
    LL z=x;x=y,y=z-(a/b)*y;
    return d;
}
inline LL crt()
{
    LL ans=0;
    for(LL i=1;i<=n;i++)
    {
        LL x,y;
        exgcd(M/a[i],a[i],x,y);
        x=(x%a[i]+a[i])%a[i];
        ans+=M/a[i]*x*b[i];
        ans%=M;
    }
    return ans;
}
int main()
{
    scanf("%d",&n);
    for(LL i=1;i<=n;i++) scanf("%lld%lld",&a[i],&b[i]),M*=a[i];
    printf("%lld",crt());
    return 0;
}

EX_CRT：

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#define LL long long
#define debug cout<<"bug"<<endl
using namespace std;
inline int exgcd(LL a,LL b,LL &x,LL &y)
{
    if(b==0){
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,x,y);
    LL z=x;
    x=y,y=z-y*(a/b);
    return d;
}
int n,flag;
LL a1,m1,a,m,lcm,x,y,d,t,c;
int main()
{
    while(~scanf("%d",&n))
    {
        flag=0; 
        scanf("%lld%lld",&a1,&m1);
        n--;
        while(n--)
        {
            scanf("%lld%lld",&a,&m);
            if(flag) continue;
            c=m-m1;
            d=exgcd(a1,a,x,y);
            if(c%d) 
            {
                flag=1;
                continue;
            }
            x=x*c/d;
            a/=d;
            x=(x%a+a)%a;
            m1=m1+x*a1;
            a1*=a; 
        }
        if(flag) printf("-1\n");
        else printf("%lld\n",m1);
    }

    return 0;
}