中国剩余定理（余数定理）Chinese remainder

int //扩展欧几里得定理 ax + by = gcd(a,b) = r . Extend_Gcd(int a, int b, int &x, int &y) { if (!b) { x = 1; y = 0; return a; } else { int r = Extend_Gcd(b, a%b, y, x);//递归直到得出最大公约数r。 y -= a / b*x; return r; } } int //中国剩余定理（余数定理）Chinese remainder Crt(int a[], int m[], int n ){ int M = 1; for (int i = 0; i < n; ++i ) M *= m[i]; int ans = 0; for (int i = 0; i < n; ++i){ int x, y; int tm = M / m[i]; Extend_Gcd( tm, m[i], x, y); ans = (ans + tm * x * a[i]) % M; } return (ans + M) % M; }

实战训练：

UVA, 756 BiorhythmsUVA原题链接

本校ACM链接

AC代码，注意，结尾处有个陷阱 就是 res<D的情况。

#include <cstdio> #define ll long long int const N = 3; ll a[N], m[N] = { 23,28,33 }, Lcm, D; //扩展欧几里得定理 ax + by = gcd(a,b) = r . void gcd(ll a, ll b, ll &d, ll &x, ll &y ){ if ( !b ) { d = a; x = 1, y = 0; } else { gcd( b, a%b, d, y, x ); y -= (a / b)*x; } } //中国剩余定理（余数定理）Chinese remainder ll China(int n, ll *m, ll *a){ ll M = 1, d, y, x = 0; for (int i = 0; i<n; i++) M *= m[i]; Lcm = M; for (int i = 0; i<n; i++) { ll w = M / m[i]; gcd(m[i], w, d, d, y); x = (x + y*w*a[i]) % M; } if (x != 0) return (x + M) % M; else return M; } int main(){ int cas = 1; ll res; while (scanf("%lld %lld %lld %d",&a[0],&a[1],&a[2],&D ) != EOF ) { if ( a[0]<0 ) break; res = China(N, m, a); while (res < D) res += Lcm; printf("Case %d: the next triple peak occurs in %lld days.\n", cas++, res - D ); } return 0; }