中国剩余定理模板题（关于中国剩余定理，我是在这里学的：）

由题可知：

　　n-ai=k*bi  --->  n-ai ≡ 0 (mod bi)  --->  n≡ai (mod bi)

直接用中国剩余定理解同余方程组就好了

注意一些坑点：

1. ai可能为负

因为 ai 是在模 bi 意义下的，所以可以很容易地转成正数： ai=(ai%bi+bi)%bi

2. 相乘过程中会爆 long long

这时我们要用神奇的O(1)快速乘... 当然你要用龟速乘也可以...

具体看代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;typedef long long ll;ll mo=1;inline ll ksc(ll x,ll y)//O(1)快速乘{    ll tmp=(x*y-(ll)((long double)x/mo*y+1.0e-8)*mo);    return tmp<0 ? tmp+mo : tmp;}void exgcd(ll a,ll b,ll &x,ll &y){    if(!b) { x=1,y=0; return; }    exgcd(b,a%b,x,y);    ll t=x; x=y;    y=t-a/b*y;}const int N=107;ll a[N],b[N],ans,n,x,y;ll China(){    for(int i=1;i<=n;i++) mo*=b[i];    for(int i=1;i<=n;i++)    {        ll m=mo/b[i];        exgcd(m,b[i],x,y);        if(x<0) x=(x%b[i]+b[i])%b[i];        ans=(ans+ksc( ksc(x,a[i]) , m) )%mo;    }    if(ans<0) ans=ans+mo;//注意答案的符号    return ans;}int main(){    cin>>n;    for(int i=1;i<=n;i++) cin>>a[i];    for(int i=1;i<=n;i++) cin>>b[i];    for(int i=1;i<=n;i++) a[i]=(a[i]%b[i]+b[i])%b[i];//注意转成正数    cout<