X问题
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 4630 Accepted Submission(s): 1520
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
HDU 2007-1 Programming Contest
中文题目，题意不再赘述，很明显，题目是要求求出在这个范围内中国剩余定理解得个数，题目并没有说明给出的每一个a[i]都是相互互质的，我们需要用到中国剩余定理非互质的模板求出最小的解，设d为中国剩余定理的最小解，不难想到k*Lcm(a1,a2,a3……an)+d(k为常数)同样也为原同余函数的解……小编还是给个证明吧……
设A%C == 0,B%C != 0,则一定存在(k*A+B)%C == B%C。(证明毕……)
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int exGcd(int a,int b,int &x,int &y)
{if(a == 0 && b == 0) return -1;if(b == 0){x = 1;y = 0;return a;}int d = exGcd(b,a%b,y,x);y -= a/b*x;return d;
}
int main()
{int n,m,t,m1,m2,r1,r2,flag;int a[11],b[11];cin>>t;while(t--){cin>>n>>m;for(int i = 0; i < m; i++)cin>>a[i];for(int i = 0; i < m; i++)cin>>b[i];flag = 0; m1 = a[0]; r1 = b[0];for(int i = 1; i < m; i++){int x,y;m2 = a[i]; r2 = b[i];int d = exGcd(m1,m2,x,y);int c = r2-r1;if(c % d){flag = 1;break;}int tmp = m2 / d;x = (c / d * x % tmp + tmp) % tmp;r1 = r1 + x * m1;m1 = m1 / d * m2;}if(flag || n < r1) cout<<0<<endl;else{int ans = (n - r1) / m1 + 1;if(r1 == 0) ans--;cout<<ans<<endl;}}return 0;
}