首页 > 代码库 > HDU1370(中国剩余定理)

HDU1370(中国剩余定理)

昨天我仔细一想,发现自己之前的分类(用OJ来划分,毫无意义啊!)太失败了,所以我重新划分了一下大分类,在分到数论的时候,我就想起了中国剩余定理了,于是乎今天就刷了一题中国剩余定理的题目了,话说太久没作数学题,导致我连样例都调了好多次(在算逆元时候老是算错~烦恼!),好在提交时候是1A。

题目的意思就是:人有三个周期,记为p,e,i,周期天数分别为23,28,33,现在给定你三个时间a,b,c,和一个天数d,a,b,c分别表示p,e,i出现的天数,问下一次出现的大于d的天数是今年的第几天,即输出天数X-d.因为23,28,33互素,所以就可以用中国剩余定理啦!否则的话,只能分解了!上学期学数论的时候很多时候多是要自己分解~

对于28*33,23*33,23*28分别求逆元(不知道什么是逆元的话,你可以理解为n是n‘ mod m的逆元,当且仅当n*n‘ mod m=1),得到6,19,2.

之后答案就是ans=6*28*33*a+19*23*33*b+2*23*28*c + k*(23*28*33),这个k要取到ans>d

ACcode

/***********************************************************
	> OS     : Linux 3.2.0-60-generic #91-Ubuntu
	> Author : yaolong
	> Mail   : dengyaolong@yeah.net 
	> Time   : 2014年06月09日 星期一 07:34:32
 **********************************************************/
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
int b[5];
int main(){

    int a;
    //23,28,33
    int m=23*28*33;
    int M[]={6,19,2};
    int M_[]={28*33,23*33,23*28};
    cin>>a;

    int ind=1;
    while(cin>>b[0]>>b[1]>>b[2]>>b[3]){
        if(b[0]==-1&&b[1]==-1&&b[2]==-1&&b[3]==-1){
            return 0;
        }
        int ans=0;
        for(int i=0;i<3;i++){
         ans=(ans+M[i]*M_[i]*b[i])%m;
        }
        while(ans<=b[3]){
            ans+=m;
        }
        cout<<"Case "<<(ind++)<<": the next triple peak occurs in "<<ans-b[3]<<" days."<<endl;

    }

return 0;
}