Biorhythms题解

分析

纯粹的板子题，知识点在这：中国剩余定理（CRT）]

注意点

• 是第一个比 d 大的数，不是最小的数
• 注意格式
• 如果结果小于 0 ，记得先加上 21252，再减 d

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
using namespace std;
long long m[]= {0,23,28,33},times=1,A[5],d;

long long ExGcd(long long a,long long b,long long &x,long long &y)
{
	if(b==0)
	{
		x=1,y=0;
		return a;
	}
	long long ans=ExGcd(b,a%b,x,y);
	long long t=y;
	y=x-(a/b)*y;
	x=t;
	return ans;
}
long long inv(long long a,long long p)//无解返回 -1
{
	long long x,y;
	if(ExGcd(a,p,x,y)!=1) return -1;
	return (x%p+p)%p;//正数化
}
long long CRT(long long a[],long long m[],long long n)
{
	long long N=1,x=0;
	for(long long i=1; i<=n; ++i) N*=m[i];
	for(long long i=1; i<=n; ++i)
	{
		long long r=N/m[i];
		x+=(r * inv( r , m[i] ) * a[i])%N;
	}
	if(x<=0) x+=21252;
	else x%=21252;
	while(x<d) x+=N;
	return x;
}
int main()
{

	while(1)
	{
		bool flag=1;
		for(long long i=1; i<=3; ++i)
		{
			cin>>A[i];
			if(A[i]!=-1) flag=false;
		}
		cin>>d;
		if(d!=-1) flag=false;
		if(flag) break;


		cout<<"Case "<<times++<<": the next triple peak occurs in "<<CRT(A,m,3)-d<<" days."<<endl;

	}


	return 0;
}