上一次刷过这道题是暴力,几年前了。
这一次用了中国剩余定理。发博以表纪念(雾)

没有图,不用点进来看了w

Code

// Code by ajcxsu
// Problem: POJ1006

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;

const int N=3;
int a[N],pm=1,m[N],M[N],IM[N];

void exgcd(int a,int b,int &x,int &y) {
    if(!b) {
        x=1, y=0;
        return;
    }
    int x1,y1;
    exgcd(b,a%b,x1,y1);
    x=y1, y=x1-a/b*y1;
}

int main() {
    ios::sync_with_stdio(false);
    /* init */
    m[0]=23,m[1]=28,m[2]=33;
    pm=23*28*33;
    for(int i=0;i<3;i++) {
        M[i]=pm/m[i];
        register int x,y;
        exgcd(M[i],m[i],x,y);
        IM[i]=x;
    }
    int x,y;

    int a,b,c,d,cas=0;
    while(cin>>a>>b>>c>>d,a!=-1) {
        a%=23, b%=28, c%=33;
        a=23-(d-a)%23, b=28-(d-b)%28, c=33-(d-c)%33;
        int ans=((a*M[0]*IM[0]+b*M[1]*IM[1]+c*M[2]*IM[2]) % pm + pm) % pm;
        if(!ans) ans+=pm;
        cout<<"Case "<<++cas<<": the next triple peak occurs in "<<ans<<" days."<<endl;
    }
    return 0;
}

模板, 代码存档, POJ, 中国剩余定理

添加新评论