题解看代码注释!
老老实实用中国剩余定理,另附加exgcd、求逆元、中国剩余定理函数接口模版
C++ 代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
/*
中国剩余定理:
对于一元线性同余方程组{x≡ai(mod mi)}且对任意i≠j满足gcd(mi,mj)==1:
设M=∏mi,Mi=M/mi,Mi模mi意义下的逆为Mi',则x=∑(ai*Mi*Mi')
*/
//扩展欧几里得
std::tuple<ll,ll,ll> exgcd(ll a,ll b){
if(a==0)return make_tuple(b,0,1);
auto [d,x,y]=exgcd(b%a,a);
return make_tuple(d,y-(b/a)*x,x);
}
//求逆元
ll inv(ll a,ll p){
//a与p不满足互质时输出-1,无逆元
//注意p原则上不能为0、1
auto[d,x,y]=exgcd(a,p);
while(x<0)x+=p;//保证逆元为正数
return d==1?x%p:-1;
}
//中国剩余定理求解x,需保证mi两两互质!
ll C_res(ll a[],const ll m[],int n){
ll _M=1,_x=0,Mi,_Mi;
for(int i=1;i<=n;i++){
_M*=m[i];
}
for(int i=1;i<=n;i++){
Mi=_M/m[i];
_Mi=inv(Mi,m[i]);
_x+=a[i]*Mi*_Mi;
}
return _x;
}
signed main(){
ll x,d,a[4],m[4],n=3,cnt=1;
m[1]=23;
m[2]=28;
m[3]=33;
constexpr ll add = 23*28*33;
while(1){
for(int i=1;i<=n;i++){
cin >> a[i];
}
cin>>d;
if(a[1]==-1 && a[2]==-1 && a[3]==-1)break;
ll x = C_res(a,m,n);
x%=add;
while(x<=d)x+=add;
cout<<"Case "<<cnt<<": the next triple peak occurs in "<<(x-d)<<" days."<<endl;
cnt++;
}
}