X问题

    Total Submission(s): 4358 Accepted Submission(s): 1399

    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)，

hdu1573 X问题（中国剩余定理）

    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

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)

    以两个为例，则x=a1+r1*x=a2+r2*y，根据后两者就可以建立方程 r1*x-r2*y=a2-a1，扩展欧几里德可解。

    解出x之后 可知N=a1+r1+x，明显这是其中一组解，N+K*（r1*r2）/gcd都是解（每次加上最小公倍数）。

    如果有多个，则两两求，新的式子可以写成N===（a1+r1*x）（mod (r1*r2)/gcd）。

    最终解出一个答案为b1,循环为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是最大公约数" 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>