51nod 中国剩余定理

看了好久，才发现原来自己曾经用过的方法，这只是一种推广。

就是单因子勾件法。每次找到能被其中一个除数除剩一，能被其他整除的数。最后加起来，然后对总和求余。

#include<cstdio>

#include <iostream>

#include <cstring>

#include <algorithm>

usingnamespacestd;

typedeflonglong LL;

constint N =15;

void extend_gcd(LL a,LL b,LL &x,LL &y)

{

    if(b==0)

    {

        x=1;

        y=0;

        return ;

    }

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

    LL t = x;

    x = y;

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

}

LL CRT(LL a[],LL m[],LL n)

{

    LL M =1;

    LL ans =0;

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

        M *= m[i];

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

    {

        LL x, y;

        LL Mi = M / m[i];//确保通过extend_gcd()求出来的可以整除其他因子，而除以m[i]余1

        extend_gcd(Mi, m[i], x, y);

        ans = (ans + Mi * x * a[i]) % M; //x为方程Mi *x + m[i]*y=1的解, Mi*x/m[i]余数为1,所以Mi*x*a[i]就为余数为a[i]的一个数，这个参见同余定理。

    }

    if(ans <0) ans += M;

    return ans;

}

int main()

{

    LL a[N], m[N], n;

    scanf("%lld", &n);

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

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

    LL ans =CRT(a, m, n);

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

    return 0;

}