[TJOI2009]猜数字

$$\left\{\begin{matrix} x\equiv a_{1}\left ( mod \ b_{1} \right ) \\ x\equiv a_{2}\left ( mod \ b_{2} \right )\\ \cdots \\ x\equiv a_{n}\left ( mod \ b_{n} \right )\\ \end{matrix}\right.$$

其中$gcd\left ( b_{i} ,b_{j}\right )=1\left ( i\neq j,i\in n,j\in n \right )$
设

$$M=\prod_{i=1}^{n}b_{i}$$ $$M_{i}=\frac{M}{b_{i}}$$ $$r_{i}\equiv M_{i}^{-1}\left ( mod \ b_{i} \right )$$

则

$$x=\sum_{i=1}^{n}M_{i}a_{i}r_{i}$$

且在M 以内有唯一解

#include<cstdio>
#define LL long long
const int N=15;
LL a[N],b[N],M[N]={1},r[N],n,x,ans=0;
void exgcd(LL a,LL b,LL &x,LL &y)
{
    if (!b) 
    {
        x=1,y=0;
        return;
    }
    exgcd(b,a%b,y,x);
    y-=a/b*x;
}
LL mul(LL a,LL b,LL mod)
{
    LL ret=0;
    for(;b;b>>=1)
    {
        if (b&1) ret=(ret+a)%mod;
        a=(a<<1)%mod;
    }
    return ret;
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++) scanf("%lld",&b[i]);
    for(int i=1;i<=n;i++) a[i]=(a[i]%b[i]+b[i])%b[i];
    for(int i=1;i<=n;i++) M[0]*=b[i];
    for(int i=1;i<=n;i++) M[i]=M[0]/b[i];
    for(int i=1;i<=n;i++) exgcd(M[i],b[i],r[i],x);
    for(int i=1;i<=n;i++) r[i]=(r[i]%b[i]+b[i])%b[i];
    for(int i=1;i<=n;i++) 
        ans=(ans+mul(mul(a[i],M[i],M[0]),r[i],M[0]))%M[0];
    printf("%lld\n",(ans%M[0]+M[0])%M[0]);
    return 0;
}