首页 > 代码库 > 【中国剩余定理】 poj 1006
【中国剩余定理】 poj 1006
生理周期 简单模拟
对于超出23 * 28 * 33（21252）时进行求余运算即可。
#include<stdio.h>int main(){ //freopen("in.txt","r",stdin); int a,b,c,d,s,m=1; while(scanf("%d %d %d %d",&a,&b,&c,&d),(a!=-1||b!=-1||c!=-1||d!=-1)) { s=a; if(b>s) s=b; if(c>s) s=c; do { s++; }while (((s+d-a)%23!=0)|| ((s+d-b))%28!=0 ||((s+d-c)%33!=0) ); if(s>21252) s=s%21252; printf("Case %d: the next triple peak occurs in %d days.\n",m,s); m++; } return 0;}
中国剩余定理
若某数x分别被d1、、…、dn除得的余数为r1、r2、…、rn，则可表示为下式：
x=R1r1+R2r2+…+Rnrn+RD
其中R1是d2、d3、…、dn的公倍数，而且被d1除，余数为1；
R1 、R2…、
Rn是d1、d2、…、dn-1的公倍数，而且被dn除，余数为1；
D是d1、d2、…、的最小公倍数；
R是任意整数，可根据实际需要决定；
且d1、、…、必须互质，以保证每个Ri(i=1,2，…，n)都能求得.
实际上POJ1006就是中国剩余定理的典型应用
根据上面的条件求出常数R1 = 5544，R2 = 14421，R3 = 1288，D = 21252
每次给的数据中的前三个值即相当于上面的余数。
则显然：
res = R1 * Physical + R2 * Emotion + R3 * Intelligence + RD - givenDate
并且0 =< res <= D
#include <stdio.h>int main(){ int R1 = 5544, R2 = 14421, R3 = 1288, R = 21252; int ph, em, in, day; int res,i; for(i=1; 1; i++){ scanf("%d%d%d%d", &ph, &em, &in, &day); if(ph==-1)break; res = (R1 * ph + R2 * em + R3 * in - day) % R; res = (res + R - 1) % R + 1; //此步处理了负数和零的两种边界情况 printf("Case %d: the next triple peak occurs in %d days.\n", i, res); } return 0;}
提交结果：
模拟 782MS
中国剩余定理 32MS
太高端了！！！！！！
【中国剩余定理】 poj 1006
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。