Chinese remainder theorem again（中國剩餘定理+不互質版+hud1788）

 Chinese remainder theorem again Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u Submit   Status   Practice   HDU 1788 Appoint description:   System Crawler  (2015-04-27)

Description

我知道部分同學最近在看中國剩餘定理，就這個定理本身，還是比較簡單的：  

假設m1,m2,…,mk兩兩互素，則下面同餘方程組：  

x≡a1(mod m1)  

x≡a2(mod m2)  

…  

x≡ak(mod mk)  

在0<=<m1m2…mk内有唯一解。  

記Mi=M/mi(1<=i<=k),因為（Mi,mi）=1,故有二個整數pi,qi滿足Mipi+miqi=1,如果記ei=Mi/pi,那麼會有：  

ei≡0(mod mj),j!=i  

ei≡1(mod mj),j=i  

很顯然，e1a1+e2a2+…+ekak就是方程組的一個解，這個解加減M的整數倍後就可以得到最小非負整數解。  

這就是中國剩餘定理及其求解過程。  

現在有一個問題是這樣的：  

一個正整數N除以M1餘(M1 - a)，除以M2餘(M2-a), 除以M3餘(M3-a),總之， 除以MI餘(MI-a),其中（a<Mi<100 i=1,2,…I）,求滿足條件的最小的數。  

Input

輸入資料包含多組測試執行個體，每個執行個體的第一行是兩個整數I(1<I<10)和a,其中，I表示M的個數，a的含義如上所述，緊接着的一行是I個整數M1,M1...MI，I=0 并且a=0結束輸入，不處理。  

Output

對于每個測試執行個體，請在一行内輸出滿足條件的最小的數。每個執行個體的輸出占一行。  

Sample Input

2 1
2 3
0 0 
           

Sample Output

5 
           

題意：N%M[i]=M[i]-a;    另A[i]=M[i]-a;       N%M[i]=A[i];

變形就是中國剩餘定理<不互質版>：不了解可以看：http://blog.csdn.net/u010579068/article/details/45422941

題目連結：http://acm.hdu.edu.cn/showproblem.php?pid=1788

轉載請注明出處：http://blog.csdn.net/u010579068

我用這篇的代碼改的。

#include<stdio.h>
#define LL __int64

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;}
    gcd(b,a%b);
}

LL M[55],A[55];


LL China(int r)
{
    LL dm,i,a,b,x,y,d;
    LL c,c1,c2;
    a=M[0];
    c1=A[0];
    for(i=1; i<r; i++)
    {
        b=M[i];
        c2=A[i];
        exgcd(a,b,d,x,y);
        c=c2-c1;
        if(c%d) return -1;//c一定是d的倍數，如果不是，則，肯定無解
        dm=b/d;
        x=((x*(c/d))%dm+dm)%dm;//保證x為最小正數//c/dm是餘數，系數擴大餘數被
        c1=a*x+c1;
        a=a*dm;
    }
    if(c1==0)//餘數為0，說明M[]是等比數列。且餘數都為0
    {
        c1=1;
        for(i=0;i<r;i++)
            c1=c1*M[i]/gcd(c1,M[i]);
    }
    return c1;
}
int main()
{
    int I,r;
    while(scanf("%d%d",&I,&r),(I+r))
    {
        for(int i=0;i<I;i++)
        {
            scanf("%I64d",&M[i]);
            A[i]=M[i]-r;
        }

        LL ans=China(I);
        printf("%I64d\n",ans);

    }
    return 0;
}