POJ 1006-Biorhythms(CRT)-白红宇

POJ 1006-Biorhythms(CRT)

阅读量：2029 次

发布时间：2019-04-28

本文共 1122 字，大约阅读时间需要 3 分钟。

题意：人自出生起就有体力，情感和智力三个生理周期，分别为23，28和33天。一个周期内有一天为峰值，在这一天，人在对应的方面（体力，情感或智力）表现最好。通常这三个周期的峰值不会是同一天。现在给出三个日期，分别对应于体力，情感，智力出现峰值的日期。然后再给出一个起始日期，要求从这一天开始，算出最少再过多少天后三个峰值同时出现。

思路：中国剩余定理(CRT)的互质板子题。

对于中国剩余定理的表述：

设m1,m2,m3….mk两两互素，则同余方程组

有整数解。并且在模M=m1*m2*……*mk下的解是唯一的，解为：

其中Mi=M/m[i]，而Mi^-1为Mi模m[i]的逆元。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             using namespace std;typedef __int64 LL;void exgcd(int a,int b,int &x,int &y){ if(b==0){ x=1;y=0; return ; } exgcd(b,a%b,x,y); int t=x; x=y; y=t-(a/b)*y;}int CRT(int a[],int m[],int n){ int M=1; int ans=0; for(int i=1;i<=n;i++){ M*=m[i]; } for(int i=1;i<=n;i++){ int x,y; int Mi=M/m[i]; exgcd(Mi,m[i],x,y); ans=(ans+Mi*x*a[i])%M; } if(ans<0) ans+=M; return ans;}int main(){ int p,e,i,d; int a[4],m[4]; int icase=1; while(~scanf("%d %d %d %d",&p,&e,&i,&d)){ if(p==-1&&e==-1&&i==-1&&d==-1) break; a[1]=p;a[2]=e;a[3]=i; m[1]=23;m[2]=28;m[3]=33; int ans=CRT(a,m,3); if(ans<=d) ans+=21252; printf("Case %d: the next triple peak occurs in %d days.\n",icase,ans-d); } return 0}

你可能感兴趣的文章

OpenCV像素点邻域遍历效率比较，以及访问像素点的几种方法