POJ 1006 Biorhythms 中国剩余定理

逗比水题...中国剩余定理(适用于互质情况)

离线算:

k1 % 23 == 0 &&  k1 % 28 == 0 && k1 % 33 == 1

k2 % 23 == 0 &&  k2 % 28 == 1 && k3 % 33 == 0

k3 % 23 == 1 &&  k3 % 28 == 0 && k3 % 33 == 0

ans = (k1*p + k2*e + k3*i) % 21252 

因为还有天数d 就减d再取模 直接输出就行了

/********************* Template ************************/
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;

#define EPS         1e-8
#define MAXN        1005
#define MOD         (int)1e9+7
#define PI          acos(-1.0)
#define DINF        (1e10)
#define LINF        ((1LL)<<50)
#define INF         (0x3f3f3f3f)
#define max(a,b)    ((a) > (b) ? (a) : (b))
#define min(a,b)    ((a) < (b) ? (a) : (b))
#define max3(a,b,c) (max(max(a,b),c))
#define min3(a,b,c) (min(min(a,b),c))
#define BUG         cout<<"BUG! "<<endl
#define line        cout<<"--------------"<<endl
#define L(t)        (t << 1)
#define R(t)        (t << 1 | 1)
#define Mid(a,b)    ((a + b) >> 1)
#define lowbit(a)   (a & -a)
#define FIN         freopen("in.txt","r",stdin)
#define FOUT        freopen("out.txt","w",stdout)
#pragma comment     (linker,"/STACK:102400000,102400000")

typedef long long LL;
// typedef unsigned long long ULL;
// typedef __int64 LL;
// typedef unisigned __int64 ULL;
LL gcd(LL a,LL b){ return b ? gcd(b,a%b) : a; }
LL lcm(LL a,LL b){ return a / gcd(a,b) * b; }

/*********************   F   ************************/int main()
{
    LL p,e,i,d;
    int cas = 1;
    LL x1 = lcm(28,33);
    for(int i = x1 ; ; i += x1){
        if(i % 23 == 1) {
            x1 = i;
            break;
        }
    }
    LL x2 = lcm(23,33);
    for(int i = x2 ; ; i += x2){
        if(i % 28 == 1) {
            x2 = i;
            break;
        }
    }
    LL x3 = lcm(23,28);
    for(int i = x3 ; ; i += x3){
        if(i % 33 == 1) {
            x3 = i;
            break;
        }
    }
    while(cin>>p>>e>>i>>d){
        if(p==-1 && e==-1 && i==-1 && d==-1) break;
        LL days = (x1 * p + x2 * e + x3 * i - d + 21252) % (23 * 28 * 33);
        cout<<"Case "<<cas++<<": the next triple peak occurs in ";
        cout<<(days ? days : 21252)<<" days."<<endl;
    }
    return 0;
}