中国剩余定理

#include<iostream>
#include<stdio.h>
using namespace std;
int ext_gcd(int a,int b,int *x,int *y)
{
    if(b==0)
    {
        *x=1,*y=0;
        return a;
    }
    int r = ext_gcd(b,a%b,x,y);
    int t =*x;
    *x=*y;
    *y=t-a/b**y;
    return r;
}
int chinese_remainder(int a[],int w[],int len)//a存放余数，w存放两两互质的数
{
    int i,d,x,y,m,n,ret;
    ret=0;
    n=1;
    for(i=0; i<len; i++)
    {
        n*=w[i];
    }
    for(i=0; i<len; i++)
    {
        m=n/w[i];
        d=ext_gcd(w[i],m,&x,&y);
        ret=(ret+y*m*a[i])%n;
        /*
　　　　　　我们知道ext_gcd可以计算：ax+by=gcd(a,b)对应的gcd，和x，y。
          当gcd(a,b)=1时：
　　　　　　ax+by=1==>by=1+(-a)*x.
　　　　　　即：b*y%a=1，根据中国剩余定理，在*对应的余数，即求得一个分项ni，累加之后，对余数的乘积取最小值，即为答案。
　　　　　　不懂分项ni是啥的可以点这里看中国剩余定理的分析。
　　　　　　这道题是hdu1370.
        */
    }
    return(ret%n+n)%n;
}
int main()
{
    int a[5];
    int w[]= {23,28,33};
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int cas=1;
        int d;
        while(scanf("%d%d%d%d",&a[0],&a[1],&a[2],&d))
        {
            if(a[0]==-1) break;
            for(int i=0; i<3; i++)
                a[i]%=w[i];
            int ans=chinese_remainder(a,w,3);
            ans=ans-d;
            if(ans<=0) ans+=21252;
            printf("Case %d: the next triple peak occurs in %d days.
",cas++,ans);

        }
    }
    return 0;
}