求在小于等于N的正整数中有多少个X满足：X mod a00 = b00, X mod a11 = b11, X mod a22 = b22, …, X mod aii = bii, … (0 < aii <= 10)。 Input 输入数据的第一行为一个正整数T，表示有T组测试数据。每组测试数据的第一行为两个正整数N，M (0 < N <= 1000,000,000 , 0 < M <= 10)，表示X小于等于N，数组a和b中各有M个元素。接下来两行，每行各有M个正整数，分别为a和b中的元素。 Output 对应每一组输入，在独立一行中输出一个正整数，表示满足条件的X的个数。 Sample Input 3 10 3 1 2 3 0 1 2 100 7 3 4 5 6 7 8 9 1 2 3 4 5 6 7 10000 10 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 Sample Output 1 0 3
#include<iostream> #include<cstdio> using namespace std; typedef long long ll; ll extendGCD(ll a,ll b,ll&x,ll&y) { if(!b){x=1;y=0;return a;} ll res=extendGCD(b,a%b,x,y); ll temp=x; x=y; y=temp-(a/b)*y; return res; } ll gcd(ll a,ll b) { return a%b==0?b:gcd(b,a%b); } bool merg(ll a1,ll m1,ll a2,ll m2,ll& a3,ll& m3)//合并两个同余方程的板子 { ll c; ll d=gcd(m1,m2); if(a1<a2) { ll temp=a1; a1=a2; a2=temp; temp=m1; m1=m2; m2=temp; } c=a1-a2; if(c%d!=0) return false; else { ll x,y; extendGCD(m2,m1,x,y); while(x<0) { x+=m1/d; } a3=a2+x*m2/d*c; m3=m1/d*m2; a3%=m3; return true; } } int a[15]; int m[15]; int main() { int t; int num,n; cin>>t; while(t--) { bool sign=true; scanf("%d%d",&num,&n); for(int i=0;i<n;i++) scanf("%d",m+i); for(int i=0;i<n;i++) scanf("%d",a+i); long long m3=m[0],a3=a[0]; for(int i=1;i<n;i++) { if(!merg(a3,m3,a[i],m[i],a3,m3)) { sign=false; break; } } //cout<<a3<<" "<<m3<<endl; if(!sign)cout<<0<<endl; else if(num<a3)cout<<0<<endl; else { ll ans=(num-a3)/m3+1; if(a3==0) ans--; cout<<ans<<endl; } } return 0; }