拓展中国剩余定理（ex_crt）

一般来讲，crt（中国剩余定理）比较常见，而ex_crt（拓展中国剩余定理）不是很常用

但是noi 2018偏偏考了这么个诡异的东西...

所以这里写一个ex_crt模板

模型：

求一个x满足上述方程，其中a1,a2...an不一定互质

解法：

设存在一特解x0满足前k个方程组，且LCM（a1,a2...ak）=M

则前k个方程的通解x=x0+k·M（k∈Z）

这是很显然的，因为 （1<=i<=k）

那么第k+1个方程等价于：求使的t值

这显然可以使用ex_gcd求解（移项即可）

那么剩余部分就简单了：不断维护一个x0，最后返回x0即可

#include <cstdio>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <queue>

#include <stack>

#define ll long long

using namespace std;

ll n;

ll a[];

ll b[];

ll pow_add(ll x,ll y,ll mod)

{

    ll ans=;

    while(y)

    {

        if(y%)

        {

            ans+=x;

            ans%=mod;

        }

        y/=;

        x+=x;

        x%=mod;

    }

    return ans;

}

ll gcd(ll x,ll y)

{

    if(y==)

    {

        return x;

    }

    return gcd(y,x%y);

}

void ex_gcd(ll a,ll b,ll &x,ll &y)

{

    if(b==)

    {

        x=;

        y=;

        return;

    }

    ex_gcd(b,a%b,x,y);

    ll t=x;

    x=y;

    y=t-(a/b)*x;

}

ll ex_crt()

{

    ll M0=a[];

    ll ans=b[];

    for(int i=;i<=n;i++)

    {

        ll r=gcd(M0,a[i]);

        ll bb=((b[i]-ans)%a[i]+a[i])%a[i];

        if(bb%r)

        {

            return -;

        }

        bb/=r;

        ll M=M0/r;

        ll aa=a[i]/r;

        ll x,y;

        ex_gcd(M,aa,x,y);

        x=pow_add(x,bb,aa);

        ans+=x*M0;

        M0*=aa;

        ans=(ans%M0+M0)%M0;

    }

    return (ans%M0+M0)%M0;

}

int main()

{

    scanf("%lld",&n);

    for(int i=;i<=n;i++)

    {

        scanf("%lld%lld",&a[i],&b[i]);

    }

    printf("%lld\n",ex_crt());

    return ;

}