X問(wèn)題
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 4358 Accepted Submission(s): 1399
Problem Description 求在小于等于N的正整數(shù)中有多少個(gè)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)，
hdu1573 X問(wèn)題（中國(guó)剩余定理）
。Input 輸入數(shù)據(jù)的第一行為一個(gè)正整數(shù)T，表示有T組測(cè)試數(shù)據(jù)。每組測(cè)試數(shù)據(jù)的第一行為兩個(gè)正整數(shù)N，M (0 < N <= 1000,000,000 , 0 < M <= 10)，表示X小于等于N，數(shù)組a和b中各有M個(gè)元素。接下來(lái)兩行，每行各有M個(gè)正整數(shù)，分別為a和b中的元素。
Output 對(duì)應(yīng)每一組輸入，在獨(dú)立一行中輸出一個(gè)正整數(shù)，表示滿足條件的X的個(gè)數(shù)。
Sample Input
310 31 2 30 1 2100 73 4 5 6 7 8 91 2 3 4 5 6 710000 101 2 3 4 5 6 7 8 9 100 1 2 3 4 5 6 7 8 9
Sample Output
103
Author lwg
Source HDU 2007-1 Programming Contest
題意：中文題，意思不多說(shuō)。 分析：
N ≡ a1(mod r1)
N ≡ a2(mod r2)
以兩個(gè)為例，則x=a1+r1*x=a2+r2*y，根據(jù)后兩者就可以建立方程 r1*x-r2*y=a2-a1，擴(kuò)展歐幾里德可解。
解出x之后 可知N=a1+r1+x，明顯這是其中一組解，N+K*（r1*r2）/gcd都是解（每次加上最小公倍數(shù)）。
如果有多個(gè)，則兩兩求，新的式子可以寫(xiě)成N===（a1+r1*x）（mod (r1*r2)/gcd）。
最終解出一個(gè)答案為b1,循環(huán)為a1
#include<iostream>#include<cstdio>#include<cstring>#include<stack>#include<queue>#include<map>#include<set>#include<vector>#include<cmath>#include using namespace std;const double eps = 1e-6;const double pi = acos(-1.0);const int INF = 0x3f3f3f3f;const int MOD = 1000000007;#define ll long long#define CL(a) memset(a,0,sizeof(a))ll A[15],B[15];ll ans,dg;void exgcd(ll a, ll b, ll &d, ll&x, ll &y){ if (!b) {d=a; x=1; y=0;} else { exgcd(b, a%b, d, y, x); y-=x*(a/b); }}ll gcd(ll a, ll b){ if (!b) return a; else gcd(b, a%b);}ll china(ll n){ ll a,b,d,x,y,dm; ll c,c1,c2; a=A[0]; c1=B[0]; for (int i=1; i<n; a="a*b/d;" b="A[i];" c="c2-c1;" c1="a*x+c1;" c2="B[i];" cin="" dg="a;//dg是最大公約數(shù)" dm="b/d;" for="" i="0;" if="" int="" ll="" main="" return="" x="">>T; while (T--) { cin>>N>>M; for (int i=0; i<m; cin="">>A[i]; for (int i=0; i<m; cin="">>B[i]; ans=china(M); //cout<N) cout<<0<<endl; else="" pre="" return=""></p></endl;></m;></m;></n;></cmath></vector></set></map></queue></stack></cstring></cstdio></iostream>