POJ 1006

解題思路：中國剩余定理

a ≡ B[1](mod m[1])  

a ≡ B[2](mod m2])  
........  
a ≡ B[n](mod mn])  
其中W,B已知，W[i]>0且W[i]與W[j]互質, 求a 
a = (M1’*M1*b1)+(M2’*M2*b2)+…+(Mk’*Mk*bk) mod m;   
其中
m = m1*m2*…*mk;
Mi = m / mi;          
Mi’是Mi關於模mi的逆元
Mi * Mi’ = 1（mod mi）
根據擴展歐幾裡得推出：Mi * Mi' + mi * x = 1

[cpp] 
#include<iostream> 
using namespace std; 
__int64 W[3]={23,28,33};//存除數 
__int64 B[3];//存余數 
__int64 ext_euclid(__int64 a,__int64 b,__int64 &x,__int64 &y) 
{ 
    if(b==0) 
    { 
        x=1; 
        y=0; 
        return a; 
    } 
    __int64 d=ext_euclid(b,a%b,x,y); 
    __int64 temp=x; 
    x=y; 
    y=temp-a/b*y; 
    return d; 
} 
 
__int64 china(__int64 *W,__int64 *B,__int64 k) 
{ 
    __int64 i; 
    __int64 d,x,y,a=0,m,n=1; 
    for(i=0;i<k;i++) 
        n*=W[i]; 
    for(i=0;i<k;i++) 
    { 
        m=n/W[i]; 
        d=ext_euclid(W[i],m,x,y); 
        a=(a+y*m*B[i])%n; 
    } 
    if(a>0)return a; 
    else return a+n; 
} 
 
int main() 
{ 
    __int64 a,b,c,d; 
    int i=1; 
    while(1) 
    { 
        scanf("%I64d%I64d%I64d%I64d",&a,&b,&c,&d); 
        if(a==-1 && b==-1 && c==-1 && d==-1)break; 
        B[0]=a;B[1]=b;B[2]=c; 
        __int64 t=china(W,B,3); 
        cout<<"Case "<<i++<<": the next triple peak occurs in "; 
        printf("%I64d",t-d); 
        cout<<" days."<<endl; 
    } 
    return 0; 
}