Biorhythms

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1196 字

体力/情感/智力周期分别为23/28/33天

一本通
练习

正文

/*
原题：「一本通 6.4 练习 3」Biorhythms（POJ 1006）
题意：体力/情感/智力周期分别为 23/28/33 天，给定三个高峰出现日 p,e,i 及当前日 d，求从 d 之后(不含 d)最早三个高峰同天距 d 的天数。
思路：即解同余方程组 x≡p(mod 23), x≡e(mod 28), x≡i(mod 33)，用扩展欧几里得两两合并(中国剩余定理)，得到最小非负解后再上调到 > d，答案即 x-d。
复杂度：O(1) 每组。
易错点：合并时注意整除条件与取最小非负解；若解 ≤ d 需加 lcm=21252；输出格式为 "Case k: the next triple peak occurs in X days."。
*/
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1;y=0;
        return a;
    }
    ll x1,y1;
    ll g=exgcd(b,a%b,x1,y1);
    x=y1;
    y=x1-(a/b)*y1;
    return g;
}
// 合并 x≡r1(mod m1), x≡r2(mod m2)，返回最小非负解（保证有解）
ll crt2(ll r1,ll m1,ll r2,ll m2){
    ll k,u;
    ll g=exgcd(m1,m2,k,u);
    ll t=(r2-r1)/g;
    ll L=m1/g*m2;
    __int128 x=r1+(__int128)m1*k*t;
    ll ans=((ll)(x%L)+L)%L;
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int p,e,i,d,cas=0;
    while(cin>>p>>e>>i>>d){
        if(p==-1&&e==-1&&i==-1&&d==-1)break;
        cas++;
        ll x12=crt2(p,23,e,28);
        ll ans=crt2(x12,23LL*28,i,33);
        while(ans<=d)ans+=21252LL;
        cout<<"Case "<<cas<<": the next triple peak occurs in "<<ans-d<<" days.\n";
    }
    return 0;
}

Biorhythms

正文

一本通·提高篇的其它内容