Biorhythms

链接：http://poj.org/problem?id=1006
思路：
中国剩余定理水题
贴一个中国剩余定理：

逆元不能用快速幂，而要用exgcd来求，之前没有注意，快速幂求逆元是费马小定理要求模数是质数的时候才可以。
代码：

#include <iostream>  
#include <stdio.h>  
#include <string.h>   
#include <stack>  
#include <queue>   
#include <map>  
#include <set>  
#include <vector>  
#include <math.h>  
#include <bitset>  
#include <algorithm>  
#include <climits>

using namespace std;
typedef long long ll;

ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if(b == 0) {x = 1; y = 0; return a;}
    ll d = exgcd(b, a%b, y, x);
    y = y - a/b * x;
    return d;
}

ll china(int n, ll *m, ll *a)
{
    ll M = 1, res = 0;
    for(int i = 0; i < n; i++) M*=m[i];
    for(int i = 0; i < n; i++) {
        ll w = M/m[i];
        ll x, y;
        exgcd(w, m[i], x, y);
        x = (x%m[i] + m[i]) % m[i];
        res = (res + a[i]*x*w % M) % M;
    }
    return res;
}

ll m[5], a[5];
int main()
{
    int cnt = 0, d;
    m[0] = 23, m[1] = 28, m[2] = 33;
    while(cin >> a[0] >> a[1] >> a[2] >> d)
    {
        if(a[0] == -1 && a[1] == -1 && a[2] == -1 && d == -1) break;
        ll ans = (china(3, m, a) - d + 21252) % 21252;
        if(ans == 0) ans = 21252;
        printf("Case %d: the next triple peak occurs in %lld days.\n",++cnt, ans);
    }
}