414
人物
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;
}
最后更新：2017-04-04 07:03:32