HDOJ1573 X问题[中国剩余定理]

X问题

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1792    Accepted Submission(s): 534

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

 

 

Recommend

linle

 

 

 

 

 

 

 

 转自：http://hi.baidu.com/nicker2010/item/da4754d5f5097c8c6cce3fed

解题思路：
1.因为(a1,a2,a3,a4,….,ak)不一定互质，所以不能够直接用中国剩余定理。
2.x=r1+a1*k1,x=r2+a2*k2,所以有r1+a1*k1=r2+a2*k2，化简后得到 a1*k1=(r2-r1) mod(a2);
用扩展欧几里得可以得到最小的k1,所以x=r1+a1*k1+a1*a2/gcd(a1,a2)，
就这样一直替换最后剩余一个同余方程。r1就是最后的解。

对于x=a1 mod b1,x= a2 mod b2，设x=a1+m*b1
所以b1*m=a2-a1 mod b2，利用欧几里德扩展定理求出最小的非负m，
那么x=a1+m*b1就已知,且x最小，如果无解，整个同余式组无解
同时，x+k*b1是所有满足x=a1 mod b1的解，而x+k'*b2又是所有满足x=a2 mod b2的解
那么，将x+k*b1与x+k'*b2合并，得到的式子就是x+k*lcm(b1,b2)
于是，上面两个式子可以用x'=x mod lcm(b1,b2)来替代
最后，就只剩下一个式子了，求得的最小的x就是答案
对于一次同余式ax=b mod n，设d=gcd(a,n)，则同余式有解的充要条件为d|b
假设d=a*x'+n*y',则x0=b/d*x'一定为方程组的一个解,且共有d个解，
（证明可以参考算法导论）最小正整数解为(x0%n/d+n/d)%(n/d)

code:

#include <iostream>
#include <vector>
using namespace std;
long long exgcd(long long a,long long b,long long &x,long long &y)
{
    if(a==0)
    {x=0;y=1;return b;}
    long long g = exgcd(b%a,a,x,y);
    long long tem = y;
    y=x;
    x=tem-(b/a)*y;
    return g;
}
long long CRT(const vector<long long>& m,const vector<long long>& b,long long& lcm)
{
    bool flag = false;
    long long x, y, i,d,result,a1,m1,a2,m2,Size=m.size();
    m1 = m[0]; a1 = b[0];
    for(i=1;i<Size;++i)
    {
        m2 = m[i]; a2 = b[i];
        d = exgcd( m1, m2, x, y );
        if((a2-a1)%d != 0) flag = true;
        result = (x * ((a2-a1) / d ) % m2 + m2 ) % m2;
        a1 = a1 + m1 * result; //对于求多个方程
        m1 = (m1 * m2) / d;    //lcm(m1,m2)最小公倍数
        a1 = (a1 % m1 + m1) % m1;
    }
    lcm = m1;
    if (flag) return -1;
    else return a1;
}
int main()
{
    long long T,N,M,i,num,ans,lcm,result;
    vector<long long> miVec,biVev;
    cin>>T;
    while(T--)
    {
        cin>>N>>M;
        miVec.clear();biVev.clear();
        for(i=0;i<M;++i)
        {cin>>num;miVec.push_back(num);}
        for(i=0;i<M;++i)
        {cin>>num;biVev.push_back(num);}
        ans = CRT(miVec,biVev,lcm);
        if(ans<0){cout<<0<<endl;continue;}
        if(N<ans) result = 0;
        else result=(N-ans)/lcm + 1;
        if(ans==0)--result;
        cout<<result<<endl;
    }
    return 0;
}

---

转自：http://yzmduncan.iteye.com/blog/1323599

数论——中国剩余定理(互质与非互质)

中国剩余定理 非互质 

中国剩余定理

     中国剩余定理是中国古代求解一次同余方程组的方法，是数论中的一个重要定理。

     设m1，m2，m3，...，mk是两两互素的正整数，即gcd(mi,mj)=1，i!=j，i,j=1,2,3,...,k.

则同余方程组：

x = a1 (mod n1)

x = a2 (mod n2)

...

x = ak (mod nk)

模[n1,n2,...nk]有唯一解，即在[n1,n2,...,nk]的意义下，存在唯一的x，满足：

x = ai mod [n1,n2,...,nk], i=1,2,3,...,k。

解可以写为这种形式：

x = sigma(ai* mi*mi') mod(N)

      其中N=n1*n2*...*nk，mi=N/ni，mi'为mi在模ni乘法下的逆元。

中国剩余定理非互质版

    中国剩余定理求解同余方程要求模数两两互质，在非互质的时候其实也可以计算，这里采用的是合并方程的思想。下面是详细推导。