X问题
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 5521 Accepted Submission(s): 1875
Problem Description
求在小于等于N的正整数中有多少个X满足：X mod a[0] = b[0], X mod a[1] = b[1], X mod a[2] = b[2], …, X mod a[i] = b[i], … (0 < a[i] <= 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
Author
lwg
Source
Recommend
linle
此题乃中国剩余定理 解模线性方程组的模板题。
1 #include "bits/stdc++.h" 2 using namespace std; 3 typedef long long LL; 4 const int MAX=15; 5 LL cas; 6 LL n,m; 7 LL aa[MAX],r[MAX],lcm; 8 LL gcd(LL a,LL b){ 9 if (b==0){ return a;}10 return gcd(b,a%b);11 }12 LL exgcd(LL a,LL b,LL &x,LL &y){13 if (b==0){x=1,y=0;return a;}14 LL d=exgcd(b,a%b,x,y),t=x;x=y,y=t-(a/b)*y;15 return d;16 }17 LL modeqset(){18 LL i,j;19 LL a,b,d,c,x,y,t;20 for (i=2;i<=n;i++){21 a=aa[i-1],b=aa[i];22 c=r[i]-r[i-1];23 d=exgcd(a,b,x,y);24 if (c%d) return -1;25 t=aa[i]/d;26 x=(x*(c/d)%t+t)%t;27 r[i]=r[i-1]+aa[i-1]*x;28 aa[i]=aa[i-1]/d*aa[i];29 }30 return r[n];31 }32 int main(){33 freopen ("x.in","r",stdin);34 freopen ("x.out","w",stdout);35 LL i,j;36 scanf("%lld",&cas);37 while (cas--){38 scanf("%lld%lld",&m,&n);39 lcm=1;40 for (i=1;i<=n;i++){41 scanf("%lld",aa+i);42 lcm=lcm/gcd(lcm,aa[i])*aa[i];43 }44 for (i=1;i<=n;i++)45 scanf("%lld",r+i);46 LL ans=modeqset();47 if (ans==-1 || ans>m){48 puts("0");49 continue;50 }51 if (ans==0)52 printf("%lld\n",(m-ans)/lcm);53 else54 printf("%lld\n",(m-ans)/lcm+1);55 }56 return 0;57 }