POJ1006 中国剩余定理

这题用到了中国剩余定理 即有方程 x=p(mod 23) x=e(mod 28) x=i(mod 33)  运用中国剩余定理求x

x-d即为答案 注意边界就可以了

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;

void exgcd(long long a,long long b,long long &d,long long &x,long long &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        d=a;
        return;
    }
    exgcd(b,a%b,d,x,y);
    long long temp=x;
    x=y;
    y=temp-(a/b)*y;
}
long long getniyuan(long long b,long long m)
{
    long long ans,gc,y;
    exgcd(b,m,gc,ans,y);
    return (ans%m+m)%m;
}
int main()
{
    long long e,i,p,d,ans,t=0;
    while(~scanf("%lld%lld%lld%lld",&p,&e,&i,&d))
    {
        if(p==-1&&e==-1&&i==-1&&d==-1)
            break;
        ans=33*28*p*getniyuan(33*28,23)+23*33*e*getniyuan(23*33,28)+28*23*i*getniyuan(28*23,33);
        ans=(ans%21252+21252)%21252;
        ans=(ans-d+21252)%21252;
        if(ans==0)
            ans=21252;
        cout<<"Case "<<++t<<": the next triple peak occurs in "<<ans<<" days."<<endl;
    }
    return 0;
}