解一系列线性同余方程。
x%m1 = a1 ...... x%mn = an 中国剩余定理 模版题。该模版为扩展版,模数不必互质
#include<iostream>
using namespace std;
#define ll long long
const int maxn=1e5+5;
const int mod = 21252;
int n;
ll exgcd(ll a,ll b,ll &x,ll &y) {
if(!b) {
x=1,y=0;
return a;
}
ll re=exgcd(b,a%b,x,y),tmp=x;
x=y,y=tmp-(a/b)*y;
return re;
}
ll m[maxn],a[maxn];
ll work() {
ll M=m[1],A=a[1],t,d,x,y;
int i;
for(i=2; i<=n; i++) {
d=exgcd(M,m[i],x,y);//解方程
if((a[i]-A)%d)return -1;//无解
x*=(a[i]-A)/d,t=m[i]/d,x=(x%t+t)%t;//求x
A=M*x+A,M=M/d*m[i],A%=M;//日常膜一膜 防爆
}
A=(A%M+M)%M;
return A;
}
int main() {
int st,ans,cnt=1;// %m[i] 余 a[i]
while(1) {
m[1] = 23;
m[2] = 28;
m[3] = 33;
n = 3;
for(int i=1; i<=3; i++)scanf("%lld",&a[i]);
scanf("%lld",&st);
if(a[1]==-1&&a[2]==-1&&a[3]==-1&&st==-1)break;
ans = (work() - st)%mod;
if(ans<=0)
ans+=mod;
printf("Case %d: the next triple peak occurs in %lld days.\n",cnt++,ans);
}
return 0;
}