X问题
题意：
中国剩余定理只能求m互为素数的情况。。。
下面是逐渐合并方程~
先求解一元线性同余方程的最小正整数解，然后看[1,n]有多少个解。
1 #include <bits/stdc++.h> 2 using namespace std; 3 int b[12],m[12]; 4 int maxv; 5 6 void exgcd(int a,int b,int &d,int &x,int &y){ 7 if(!b){d=a;x=1;y=0;} 8 else {exgcd(b,a%b,d,y,x);y-=x*(a/b);} 9 } 10 // 求解n个方程x%m[i]=b[i] 11 int solve(int* b,int* m,int n){ 12 int m1=m[0],b1=b[0];; 13 for(int i=1;i<n;i++){ 14 int m2=m[i],b2=b[i]; 15 int g,x,y; 16 exgcd(m1,m2,g,x,y); 17 int c=b2-b1; 18 if(c%g) return 0; //无解 19 x=x*(c/g); 20 int r=m2/g; 21 x=(x%r+r)%r; 22 b1+=m1*x; 23 m1*=m2/g; 24 b1%=m1; 25 } 26 int ans=(b1%m1+m1-1)%m1+1; 27 if(ans>maxv) return 0; 28 int cnt=(maxv-ans)/m1; 29 return cnt+1; 30 } 31 32 int main(){ 33 int t; 34 scanf("%d",&t); 35 while(t--){ 36 int n; 37 scanf("%d%d",&maxv,&n); 38 for(int i=0;i<n;i++) scanf("%d",&m[i]); 39 for(int i=0;i<n;i++) scanf("%d",&b[i]); 40 printf("%d ",solve(b,m,n)); 41 } 42 43 }