POJ1006 Biorhythms【中国剩余定理】

#include <iostream>
using namespace std;
int Extended_Euclid(int a,int b,int &x,int &y) 
{
    int d;
    if(b==0)
    {
        x=1;y=0;
        return a;
    }
    d=Extended_Euclid(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
int Chinese_Remainder(int a[],int w[],int num) 
{
    int i,d,x,y,m,lcm,ret;
    ret=0;
    lcm=1;
    for (i=0;i<num;i++)
        lcm*=w[i];
    for (i=0;i<num;i++)
    {
        m=lcm/w[i];
        d=Extended_Euclid(w[i],m,x,y);
        ret=(ret+y*m*a[i])%lcm;
    } 
    return (lcm+ret%lcm)%lcm;   
}

int main()
{
    int n,i,c,d,C=1,ans;
    int w[15]={23,28,33},a[15];
    while (scanf("%d %d %d %d",&a[0],&a[1],&a[2],&d)!=EOF)
    {
        if(a[1]==-1&&a[2]==-1&&a[0]==-1) break;
        a[0]%=23;
        a[1]%=28;
        a[2]%=33;
        int lcm=33*28*23;   
        ans=Chinese_Remainder(a,w,3);    
        ans=ans-d;
        if(ans<=0) ans=ans+lcm;     
        printf("Case %d: the next triple peak occurs in %d days.
", C++,ans);
    } return 0;
}