poj_1006 生理周期

题目:

  人生来就有三个生理周期,分别为体力、感情和智力周期,它们的周期长度为23天、28天和33天。每一个周期中有一天是高峰。在高峰这天,人会在相应的方面表现出色。例如,智力周期的高峰,人会思维敏捷,精力容易高度集中。因为三个周期的周长不同,所以通常三个周期的高峰不会落在同一天。对于每个人,我们想知道何时三个高峰落在同一天。对于每个周期,我们会给出从当前年份的第一天开始,到出现高峰的天数(不一定是第一次高峰出现的时间)。你的任务是给定一个从当年第一天开始数的天数,输出从给定时间开始(不包括给定时间)下一次三个高峰落在同一天的时间(距给定时间的天数)。例如:给定时间为10,下次出现三个高峰同天的时间是12,则输出2(注意这里不是3)。

思路:

  由题意可列出三条方程:
  
  
  
  然后套中国剩余定理就好了。。。
  顺便在这里写下关于中国剩余定理的总结好了。。。
  给定一个方程组:
  如果能使
  那么最终的解就等于
  而这样的,用扩展欧几里得求出逆元即可。

代码:

#include <cstdio>
#define ll long long
using namespace std;
void exgcd(ll a,ll b,ll &d,ll &x,ll &y){
    if(!b){d=a;x=1;y=0;return;}
    exgcd(b,a%b,d,y,x);y-=a/b*x;
}
ll china(int n,int a[],int m[]){
    ll M=1,x,y,d,ans=0;
    for(int i=1;i<=n;i++)
        M*=m[i];
    for(int i=1;i<=n;i++){
        ll w=M/m[i];
        exgcd(w,m[i],d,x,y);
        (ans+=x*w%M*a[i]%M)%=M;
    }
    return (ans+M)%M;
}
int A[4],MOD[4]={-1,23,28,33};
int main(){
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    int a,b,c,d,Cas=1;
    while(scanf("%d%d%d%d",&a,&b,&c,&d),a+b+c+d!=-4){
        A[1]=a-d;
        A[2]=b-d;
        A[3]=c-d;
        ll ans=china(3,A,MOD);
        if(ans==0)ans+=21252;
        printf("Case %d: the next triple peak occurs in %lld days.\n",Cas++,ans);
    }
    return 0;
}