[poj 2891] Strange Way to Express Integers 解题报告（excrt扩展中国剩余定理）

题目链接：http://poj.org/problem?id=2891

题目大意：

求解同余方程组，不保证模数互质

题解：

扩展中国剩余定理板子题

#include<algorithm>

#include<cstring>

#include<cstdio>

#include<iostream>

#include<cmath>

using namespace std;

typedef long long ll;

const int N=+;

int k;

ll m[N],a[N];

inline ll read()

{

    char ch=getchar();

    ll s=,f=;

    while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}

    while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}

    return s*f;

}

ll mul(ll a,ll b,ll mod)

{

    ll re=;

    for (;b;b>>=,a=(a+a)%mod) if (b&) re=(re+a)%mod;

    return re;

}

ll exgcd(ll a,ll b,ll &x0,ll &y0)

{

    if (!b)

    {

        x0=;y0=;

        return a;

    }

    ll gcd=exgcd(b,a%b,y0,x0);

    y0-=a/b*x0;

    return gcd;

}

ll excrt()

{

    ll M=m[],x=a[];

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

    {

        ll mi=m[i],ai=a[i];

        ll x0,y0;

        ll gcd=exgcd(M,mi,x0,y0);

        ll c=(ai-x%mi+mi)%mi;

        if (c%gcd) return -;

        x0=mul(x0,c/gcd,mi/gcd);

        //x0=x0*c/gcd%(mi/gcd);

        x+=x0*M;

        M=M/gcd*mi;

        x%=M;

    }

    return (x%M+M)%M;

}

int main()

{

    //freopen("excrt.in","r",stdin);

    //freopen("excrt.out","w",stdout);

    //scanf("%d",&k);

    while (~scanf("%d",&k))

    {

        for (int i=;i<=k;i++) m[i]=read(),a[i]=read();

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

    }

    return ;

}