数论 · 中国剩余定理（CRT）

· · 个人记录

UPDATE

问题概述

小奥里的韩信点兵问题：

\begin{cases}x\equiv{a_1}\pmod{m_1}\\x\equiv{a_2}\pmod{m_2}\\\cdots\\x\equiv{a_k}\pmod{m_k}\end{cases} ## 求解 构造一个数组 ans，使得 $\forall\ i \in [1,k]$： $$ \begin{cases}{ans_i} \equiv 0 \pmod{m_1}\\ \cdots\\ {ans_i} \equiv {a_i} \pmod{m_i}\\ \cdots \\ {ans_i} \equiv 0\pmod {m_k}\end{cases} $$ 易得： $$ ans_i = (\prod_{i=1} ^ k m_i (i\ne j)) \times a_i \times e_i $$ $e_i$ 为我们仍不知道的数。 不妨令 $M\gets \prod_{i=1} ^ k m_i $， 就可以推出：

\dfrac{M}{m_i} \times e_i \equiv 1 \pmod {m_i}

此处用扩展欧几里得求逆元，在输入时也一起统计好 $M$。 最后的答案就是：

\sum\limits_{i=1}^k ans_i\ \bmod M

## 代码实现 ```cpp #include<bits/stdc++.h> using namespace std; #define int long long #define rint register int int n, p; int x, y; inline int read () { int x = 1, s = 0; char ch = getchar (); while (ch < '0' or ch > '9') {if (ch == '-') x = -1; ch = getchar ();} while (ch >= '0' and ch <= '9') s = s * 10 + ch - '0', ch = getchar (); return x * s; } inline void write (int x) { if (x > 9) write (x / 10); putchar (x % 10 ^ 48); } inline void exgcd (int a, int b) { if (!b) { x = 1, y = 0; return; } exgcd (b, a % b); int t = x; x = y, y = t - a / b * y; } const int maxn = 15; int a[maxn], b[maxn], ans; int mul = 1, mi[maxn]; signed main () { n = read (); for (rint i (1); i <= n; ++i) { a[i] = read (), b[i] = read (); mul *= a[i]; } for (rint i (1); i <= n; ++i) { mi[i] = mul / a[i]; exgcd (mi[i], a[i]); ans += b[i] * mi[i] * (x > 0 ? x : x + a[i]); } write (ans % mul); return 0; } ``` ------------ ### 例题 [UVA756 Biorhythms](https://469672.blog.luogu.org/solution-uva756) ------------ ### EXCRT [详见：《数论 · 扩展中国剩余定理（EXCRT）》](https://www.luogu.com.cn/blog/469672/shuo-lun-kuo-zhan-zhong-guo-sheng-yu-ding-li-excrt) ------------ ——$End$——