#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> 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<iostream> #include<cstdio> #include<algorithm> #include<cstring> 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);} }