#include#include #include #include using namespace std;typedef long long LL;LL ai[4],ri[4],M;void Exgcd(LL a,LL b,LL& d,LL& x,LL& y){ if(b == 0) { d = a, x = 1, y = 0;} else { Exgcd(b,a%b,d,y,x); y -= x*(a / b); }}LL gcd(LL a,LL b){ return b == 0 ? a : gcd(b,a%b);}LL solve(int n){ LL a1,r1; LL a, b, c; LL x, y, d; a1 = ai[1], r1 = ri[1]; for(int i = 2; i <= n; ++i) { a = a1, b = ai[i], c = ri[i] - r1; Exgcd(a,b,d,x,y); if(c % d) return -1; LL t = b / d; x = (x * (c / d)% t + t) % t; r1 = a1 * x + r1; a1 = a1 *(ai[i] / d); } return r1;}int main(){ LL p,e,k,d; int Kase = 1; while(cin >> p >> e >>k >>d) { ai[1] = 23, ai[2] = 28, ai[3] = 33; ri[1] = p , ri[2] = e, ri[3] = k; if(p == -1 && e == -1 && k == -1 && d == -1) break; LL ans = solve(3); M = 1; for(int i = 1; i <= 3; ++i) M = M * ai[i] / gcd(M,ai[i]); if(ans >= M) ans %= M; // 求最小的值. while(ans <= d) ans += M; printf("Case %d: the next triple peak occurs in %lld days.\n",Kase++,ans-d); }}
中国剩余定理撸一发
不过中国剩余定理 ai[i] 需要互质
#include#include #include #include using namespace std;typedef long long LL;LL ai[4],ri[4],M;void Exgcd(LL a,LL b,LL& d,LL& x,LL& y){ if(b == 0) { d = a, x = 1, y = 0;} else { Exgcd(b,a%b,d,y,x); y -= x*(a / b); }}LL gcd(LL a,LL b){ return b == 0 ? a : gcd(b,a%b);}LL China(int n){ M = 1; LL Mi,x,y,d,ans = 0; for(int i = 1; i <= n; ++i) M *= ai[i]; for(int i = 1; i <= n; ++i) { Mi = M / ai[i]; Exgcd(Mi,ai[i],d,x,y); ans = (ans + Mi * x * ri[i]) % M; } if(ans < 0) ans += M; return ans ;}int main(){ LL p,e,k,d; int Kase = 1; while(cin >> p >> e >>k >>d) { ai[1] = 23, ai[2] = 28, ai[3] = 33; ri[1] = p , ri[2] = e, ri[3] = k; if(p == -1 && e == -1 && k == -1 && d == -1) break; LL ans = China(3); /*M = 1; for(int i = 1; i <= 3; ++i) M = M * ai[i] / gcd(M,ai[i]);*/ //if(ans >= M) ans %= M; // 求最小的值. while(ans <= d) ans += M; printf("Case %d: the next triple peak occurs in %lld days.\n",Kase++,ans-d); }}