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;
}

补充：软件开发 , C++ ,