题目地址：POJ 1006

学习了下中国剩余定理。參考的该博客。博客戳这里。

中国剩余定理的求解方法：

假如说x%c1=m1,x%c2=m2,x%c3=m3.那么能够设三个数R1,R2,R3.R1为c2,c3的公倍数且余c1为1，同理。R2,R3也是如此。然后设z=R1*m1+R2*m2+R3*m3，那么z就是当中一个解。并且每隔(c1,c2,c3)的最小公倍数就是一个解。想要最小解的话，仅仅需对最小公倍数取余即可了。

以下的代码未删改。比赛的时候为了避免超时，R1,R2,R3的求解过程全然没有必要放在程序里，自己算出来直接用上即可。

代码例如以下：

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;

#define LL __int64

int main()

{

LL a, b, c, d, R1, R2, R3, i, j, k, R, num=0;

R1=28*33;

R2=23*33;

R3=23*28;

for(i=1;; i++)

{

if(R1*i%23==1)

{

R1*=i;

break;

}

}

for(i=1;; i++)

{

if(R2*i%28==1)

{

R2*=i;

break;

}

}

for(i=1;; i++)

{

if(R3*i%33==1)

{

R3*=i;

break;

}

}

while(scanf("%I64d%I64d%I64d%I64d",&a,&b,&c,&d)!=EOF)

{

if(a<0&&b<0&&c<0&&d<0)

break;

num++;

R=R1*a+R2*b+R3*c;

LL z, ans;

z=R%21252;//21252为a，b，c的最小公倍数

if(z<=d)

{

z+=21252;

}

ans=z-d;

printf("Case %I64d: the next triple peak occurs in %I64d days.\n",num,ans);

}

return 0;

}

查看原文