从爱神那看的中国剩余定理解法，挺容易理解的，就是一个循环迭代更新下去

细节还是很重要！

1 #include
      
        2 #include
       
         3 #define LL long long 4 void exgcd(LL a,LL b,LL& d,LL &x,LL &y) 5 { 6     if (!b) {d=a; x=1; y=0;  } 7     else {exgcd(b,a%b,d,y,x); y-=x*(a/b);   } 8 } 9 int main()10 {11     LL T,n,m,i,flag,d,x,y,tmp;12     LL a[15],b[15];13     scanf("%I64d",&T);14     while (T--)15     {16         scanf("%I64d%I64d",&n,&m);17         for (i=1;i<=m;i++) scanf("%I64d",&a[i]);18         for (i=1;i<=m;i++) scanf("%I64d",&b[i]);19        flag=0;20         for (i=2;i<=m;i++)21         {22             exgcd(a[1],a[i],d,x,y);23             if ((b[i]-b[1])%d) {flag=1; break; }//只有差为gcd的倍数才存在解（exgcd）24             tmp=a[i]/d;//tmp为了防止b[i]-b[1]为负，要把下面的x使变为负25             x=(x*(b[i]-b[1])/d%tmp+tmp)%tmp;26             b[1]=a[1]*x+b[1];27             a[1]=a[1]*a[i]/d;28         }29         if (flag||b[1]>n) printf("0\n");30         else if (b[1]==0) printf("%I64d\n",n/a[1]);//注意余数为031         else printf("%I64d\n",(n-b[1])/a[1]+1);32     }33 }