X問題

    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問題（中國(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è)元素。接下來兩行，每行各有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

    題意：中文題，意思不多說。 分析：

    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è)，則兩兩求，新的式子可以寫成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>