此題本來(lái)模擬即可，但是注意有容易出錯(cuò)的地方。
這題主要是可以用中國(guó)剩余定理來(lái)做。
根據(jù)題意可以抽象出這樣的模型。給出三個(gè)數(shù)A,B,C分別是模23,28,33后的余數(shù)，求最小的數(shù)字
使得其模23,28,33分別為A,B,C，并且要大于給定的數(shù)字D。
中國(guó)剩余定理很好的解決了這種余數(shù)問(wèn)題。令模數(shù)為Ni,余數(shù)為Ai,設(shè)Mi = N1*N2*...*Ni-1*Ni+1*...*Nn，
那么答案一定滿足形式ans =
ΣAi*Mi*(Mi對(duì)Ni的乘法逆) % N。(N為所有Ni的乘積)。
很明顯，由于ans的第i項(xiàng)有Mi因子，所以模N1-Ni-1和Ni+1-Nn肯定是0，而Ai*Mi*(Mi對(duì)Ni的乘法逆) %Ni
就是Ai。這樣就滿足了要求。
代碼如下：
#include <stdio.h>
#include <algorithm>
#include <
string.h>
#include <vector>
using namespace std;
int Egcd(
int nN,
int nM,
int& nX,
int& nY)
{
if (nM == 0)
{
nX = 1, nY = 0;
return nN;
}
int nRet = Egcd(nM, nN % nM, nX, nY);
int nT = nX;
nX = nY;
nY = nT - (nN / nM) * nY;
return nRet;
}
int main()
{
int nA, nB, nC, nD;
int nDays = 21252;
int nCase = 1;
while (scanf("%d%d%d%d", &nA, &nB, &nC, &nD),
nA != -1 || nB != -1 || nC != -1 || nD != -1)
{
int nFirst = 0;
nA %= 23;
nB %= 28;
nC %= 33;
int nM1= 28 * 33, nM2 = 23 * 33, nM3 = 23 * 28;
int nN1, nN2, nN3, nTemp;
Egcd(23, nM1, nTemp, nN1);
Egcd(28, nM2, nTemp, nN2);
Egcd(33, nM3, nTemp, nN3);
nFirst = (nA * nM1 * nN1 + nB * nM2 * nN2 + nC * nM3 * nN3) % nDays;
while (nFirst <= nD)nFirst += nDays;
printf("Case %d: the next triple peak occurs in %d days.\n",
nCase++, nFirst - nD);
}
return 0;
}