1639：Biorhythms
时间限制: 1000 ms 内存限制: 524288 KB
【题目描述】
原题来自：POJ 1006
人生来就有三个生理周期，分别为体力、感情和智力周期，它们的周期长度为 23 天、28 天和 33 天。每一个周期中有一天是高峰。在高峰这天，人会在相应的方面表现出色。例如，智力周期的高峰，人会思维敏捷，精力容易高度集中。因为三个周期的周长不同，所以通常三个周期的高峰不会落在同一天。对于每个人，我们想知道何时三个高峰落在同一天。对于每个周期，我们会给出从当前年份的第一天开始，到出现高峰的天数（不一定是第一次高峰出现的时间）。
你的任务是给定一个从当年第一天开始数的天数，输出从给定时间开始（不包括给定时间）下一次三个高峰落在同一天的时间（距给定时间的天数）。
例如：给定时间为 10，下次出现三个高峰同天的时间是 12，则输出 2（注意这里不是 3）。
【输入】
本题有多组数据。
对于每组数据，输入四个整数 p,e,i和 d。p,e,i 分别表示体力、情感和智力高峰出现的时间（时间从当年的第一天开始计算）。d 是给定的时间，可能小于 p,e 或 i。
当 p=e=i=d=−1 时，输入数据结束。
【输出】
从给定时间起，下一次三个高峰同天的时间（距离给定时间的天数）。采用以下格式：
Case 1: the next triple peak occurs in 1234 days.
注意：即使结果是 1 天，也使用复数形式 days。
【输入样例】
0 0 0 0
0 0 0 100
5 20 34 325
4 5 6 7
283 102 23 320
203 301 203 40
-1 -1 -1 -1
【输出样例】
Case 1: the next triple peak occurs in 21252 days.
Case 2: the next triple peak occurs in 21152 days.
Case 3: the next triple peak occurs in 19575 days.
Case 4: the next triple peak occurs in 16994 days.
Case 5: the next triple peak occurs in 8910 days.
Case 6: the next triple peak occurs in 10789 days.
【提示】
数据范围与提示：
所有给定时间是非负的并且小于 365，所求的时间小于 21252。
sol：恶心的题面让蒟蒻的我一遍遍读错。。。
题意就是
求n满足
(n+d)%T1 = Yus1
(n+d)%T2 = Yus2
(n+d)%T3 = Yus3
（其中T和Yus已知）
随便推推，还挺裸的
原式求n满足
(n+d)%T1 = Yus1
(n+d)%T2 = Yus2
(n+d)%T3 = Yus3
转化一下就是求
N%T1 = Yus1
N%T2 = Yus2
N%T3 = Yus3 (N>d)
其中 T1=23 T2=28 T3=33
N = Yus1+T1*k1
N = Yus2+T2*k2
N = Yus3+T3*k3
Yus1+T1*k1 = Yus2+T2*k2
T1*k1-T2*k2 = Yus2-Yus1
T1*k1+T2*k2 = Yus2-Yus1 (类ax+bYus=c的形式)
求出k1,k2
Ans=T1*k1+Yus1就是一个特解 设通解为P
P=Ans+K*LCM LCM=lcm(T1,T2)
合并后式子就是 P%LCM = Ans
下一个式子就是
Ans+K*LCM = Yus3+T3*k3
k*LCM-T3*k3 = Yus3-Ans
求出k,k*LCM+Ans就是通解了
/*
原式求n满足
(n+d)%T1 = Yus1
(n+d)%T2 = Yus2
(n+d)%T3 = Yus3
转化一下就是求
N%T1 = Yus1
N%T2 = Yus2
N%T3 = Yus3 (N>d)
其中 T1=23 T2=28 T3=33 N = Yus1+T1*k1
N = Yus2+T2*k2
N = Yus3+T3*k3 Yus1+T1*k1 = Yus2+T2*k2
T1*k1-T2*k2 = Yus2-Yus1
T1*k1+T2*k2 = Yus2-Yus1 (类ax+bYus=c的形式)
求出k1,k2
Ans=T1*k1+Yus1就是一个特解 设通解为P
P=Ans+K*LCM LCM=lcm(T1,T2)
合并后式子就是 P%LCM = Ans
下一个式子就是
Ans+K*LCM = Yus3+T3*k3
k*LCM-T3*k3 = Yus3-Ans
求出k,k*LCM+Ans就是通解了
*/
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
inline ll read()
{
ll s=;
bool f=;
char ch=' ';
while(!isdigit(ch))
{
f|=(ch=='-'); ch=getchar();
}
while(isdigit(ch))
{
s=(s<<)+(s<<)+(ch^); ch=getchar();
}
return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
if(x<)
{
putchar('-'); x=-x;
}
if(x<)
{
putchar(x+''); return;
}
write(x/);
putchar((x%)+'');
return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('\n')
const int Mod=;
int T[],Yus[];
inline int gcd(int a,int b)
{
return (!b)?(a):(gcd(b,a%b));
}
inline void Exgcd(int a,int b,int &X,int &Y)
{
if(b==)
{
X=;
Y=;
return;
}
Exgcd(b,a%b,X,Y);
int XX=X,YY=Y;
X=YY;
Y=XX-a/b*YY;
return;
}
int main()
{
int i,d,Cnt=;
int a,b,c,r,X,Y,LCM,Ans;
while(true)
{
for(i=;i<=;i++)
{
Yus[i]=read();
}
d=read();
T[]=; T[]=; T[]=;
if(Yus[]==-&&Yus[]==-&&Yus[]==-&&d==-) break;
LCM=T[]; Ans=;
for(i=;i<=;i++)
{
a=T[i-]; b=T[i]; c=Yus[i]-Yus[i-]; r=gcd(a,b);
Exgcd(a,b,X=,Y=);
X=X*c/r;
int tmp=b/r;
X=(X%tmp+tmp)%tmp;
if(X==) X+=tmp;
LCM=LCM*T[i]/r;
T[i]=LCM;
Ans=X*T[i-]+Yus[i-];
Ans%=LCM;
Yus[i]=Ans;
}
while(Ans<=d) Ans+=LCM;
printf("Case %d: the next triple peak occurs in %d days.\n",++Cnt,Ans-d);
}
return ;
}
/*
input
0 0 0 0
0 0 0 100
5 20 34 325
4 5 6 7
283 102 23 320
203 301 203 40
-1 -1 -1 -1
output
Case 1: the next triple peak occurs in 21252 daYuss.
Case 2: the next triple peak occurs in 21152 daYuss.
Case 3: the next triple peak occurs in 19575 daYuss.
Case 4: the next triple peak occurs in 16994 daYuss.
Case 5: the next triple peak occurs in 8910 daYuss.
Case 6: the next triple peak occurs in 10789 daYuss.
*/