中国剩余定理学习总结

中国剩余定理学习总结

理解：

     设m1，m2，m3，...，mk是两两互素的正整数，即gcd(mi,mj)=1，i!=j，i,j=1,2,3,...,k.

则同余方程组：

x = a₁ (mod n₁)

x = a₂ (mod n₂)

...

x = a_k (mod n_k)

模(n₁,n₂,...n_k)有唯一解，即在(n₁,n₂,...,n_k)的意义下，存在唯一的x，满足：

x = a_i mod (n₁, n₂,...,n_k),i = 1, 2, 3, ..., k。

解可以写为这种形式：

ðx = sigma (a_i * m_i* m_i') mod(N)

其中N = n₁ * n₂ * ... * n_k， m_i= N / n_i，m_i'为m_i在模n_i乘法下的逆元。

思想：

通过上面的x的求法，可以比较明确的看出，我们针对一个a_x0当我们对于x 做x % n_x0时，显然，对于对应的a_x0* m_x0 * m_x0',m_x0'是对于m_x0对于mod n_x0的逆元，所以，显然对于m_x0 * m_x0' % n_x0为0，然后针对其他的项，因为所有的n_i互质，所以其他项，均mod为0，只有当前还有一个a，得证。

Source：

/*O(n log n) 中国剩余定理(crt)*/ int CRT(int *res, int *mod, int n) { int ans = 0, m = 1; for (int i = 1; i <= n; ++i) m *= mod[i]; for (int i = 1; i <= n; ++i) { int mi = m / mod[i]; ext_gcd(mi, mod[i], x, y); ans = (ans + mi * x * res[i]) % m; } if(ans < 0) ans += m; return ans; } 拓展：不互质形式

因为对于这种普通的中国剩余定理，我们必须要求要对每一个mod都保证两两互质，这样才能直接使用，但是现实是不是每一道题都能直接满足，所以我们应该要做到有通解的方法。

烤炉我们需要求取满足

m = a₁ (mod r₁)

m = a₂ (mod r₂)

...

m = a_k (mod r_k)

的一个x，那么我们提出任意两个等式

m = a₁ * x + r₁ = a₂* y + r₂

ð a₁ * x + r1 = a₂ * y+ r2

ð a₁ * x + a₂ * (-y) =r2 – r1

ð 形如 a * x + b * y = c的形式

那么直接通过扩欧就可以确定当前能取得的最小的x，

所以，针对这两个等式所求的m即为，m = a₁ * x + r₁那么詪显然的，为了满足继续的等式，并且不破坏当前的性质，即m’ % a₁ = n₁

且m’ % a₂ = r₂ 那么我们只要满足 (m’ – m) % [a₁, a₂]= 0 即可，所以对于这两个等式我们可以合并成为m’ = m (mod [a₁, a₂])

也就可以变形成为 m’ = [a₁, a₂] * x +m è 形如原来的等式m = a * x + r, 然后往后面依次计算即可。每一次联立两个等式，进行扩欧，最后得到满足所有等式的答案。

#include <cstdio> #include <algorithm> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <cctype> using namespace std; inline void R(long long &v) { char c = 0; bool p = true; v = 0; while(!isdigit(c)) { if(c == '-') p = false; c = getchar(); } while(isdigit(c)) { v = (v << 3) + (v << 1) + (c ^ '0'); c = getchar(); } if(!p) v = -v; } long long s, t, v, e, x, y, a, b, c; long long ans; long long gcd(long long a, long long b) { return (!b) ? a : gcd(b, a % b); } void ext_gcd(long long a, long long b, long long &x, long long &y) { b ? (ext_gcd(b, a % b, y, x), y -= a / b * x) : (x = 1, y = 0); } long long n, a1, r1, a2, r2; int main() { while(scanf("%lld", &n) != EOF) { bool flag = true; R(a1), R(r1); for(int i = 1; i < n; ++i) { /*因为不一定满足所有的mod都是互质的 所以我们不能用普通的CRT解决，*/ R(a2), R(r2); a = a1, b = a2, c = r2 - r1; long long t = gcd(a, b); if(c % t) { flag = false; continue; } a /= t, b /= t, c /= t; ext_gcd(a, b, x, y); x = (x % b * c % b + b) % b; /*针对任意两个算式，求取m = a1 * x + r1 = a2 * y + r2 即， a1 * x - a2 * y = r2 - r1 ==> ax + by = c 直接用扩欧解决即可， 然后对于求得的答案，因为要与下一个、 联立， 那么只要满足，新的 m' = m + C * [a1, a2]即可 然后又可以将算式，转变为m = a1 * x + r1的形式继续联立*/ long long temp = a1; a1 = t * a * b; a = x * temp + r1; r1 = a; } if(!flag) cout << "-1" << '\n'; else cout << a << '\n'; } }