poj 1006(中国剩余定理)

poj 1006
裸的中国剩余定理，注意一下负数的情况即可

#include<cstdio>    
#include<algorithm>    
#include<cstring>      
#define ms(i,j) memset(i,j, sizeof i);    
#define ll long long
using namespace std;
int p, e, i, d;
int a[4],m[4];
void e_gcd(int a, int b, int &x, int &y)
{
    if (b==0)
    {
        x=1; y=0;
        return ;
    }
    e_gcd(b,a%b,x,y);
    int t = x;
    x = y;
    y = t-y*a/b;
}
int crt(int n)
{
    int ans = 0;
    int M = 1;
    for (int i=1;i<=n;i++) M*=m[i];
    for (int i=1;i<=n;i++)
    {
        int Mi = M/m[i];
        int x,y;
        e_gcd(Mi, m[i], x, y);
        ans = (ans + Mi*a[i]*x)%M;
    }
    return (ans+M)%M;
}
int main()    
{     
    int kase = 0;
    m[1] = 23;m[2] = 28;m[3] = 33;
    while (scanf("%d%d%d%d", &p, &e, &i, &d)==4)
    {
        if(p == -1 && e == -1 && i == -1 && d == -1)  break; 
        a[1] = p; a[2] = e; a[3] = i;
        int ans = crt(3);
        ans -= d;
        if (ans<=0) ans += 21252; 
        printf("Case %d: the next triple peak occurs in %d days.\n", ++kase, ans);
    }
    return 0;    
}