中国剩余定理用来求解同余方程组。其中 \(m_i\) 两两互质
\( \begin{cases} x &\equiv a_1 \pmod {m_1}\\ x &\equiv a_2 \pmod{m_2}\\ &\vdots\\ x & \equiv a_k\pmod {m_k}\\ \end{cases} \)
定义 \(M=\prod\limits_{i=1}^km_i;\ c_i=M_i/m_i\)，\(c_i^{-1}\) 是模 \(m_i\) 意义下的逆元
\(x=\sum\limits_{i=1}^k{a_ic_ic_i^{-1}}\pmod M\)
不要以为这里的 \(c_ic_i^{-1}=1\) 模数不一样的。
如果想深入理解，我们需要知道公式是怎么来的。
我们可以参考：https://zhuanlan.zhihu.com/p/103394468、https://www.bilibili.com/video/BV1AN4y1N7Su/?spm_id_from=333.999.0.0&vd_source=700dde1e30c453844bbbd11aff30a401
我们先感性思考下，想使得 \(x\) 满足这么多方程式不容易，但是如果是……
\( \begin{cases} n_1 &\equiv a_1 \pmod {m_1}\\ n_2 &\equiv a_2 \pmod{m_2}\\ &\vdots\\ n_k & \equiv a_k\pmod {m_k}\\ \end{cases} \)
让 \(n_i\) 去满足对应的一个方程，是不是会更简单些？那么这和 \(x\) 有什么关系？难不成将 \(n_i\) 全加起来？显然不行，比如说我们考虑：
\( \begin{cases} n_1 &\equiv 2 \pmod {3}\\ n_2 &\equiv 3 \pmod{5}\\ \end{cases} \)
显然不是随意的 \(n_1+n_2\)，如果 \(x=n_1+n_2\) 的话，分别让其满足一式和二式，则 \(x\) 分别得是 \(3\)、\(5\) 的倍数。我们扩展下，来到经典例子：
\( \begin{cases} n_1 &\equiv 2 \pmod {3}\\ n_2 &\equiv 3 \pmod{5}\\ n_3 &\equiv 2 \pmod{7}\\ \end{cases} \)
运用刚才的思路，应 \(n_1\) 是 \(35\) 的倍数，\(n_2\) 是 \(21\) 的倍数，\(n_3\) 是 \(15\) 的倍数。
于是方程化为：
\( \begin{cases} 35w_1 &\equiv 2 \pmod {3}\\ 21w_2 &\equiv 3 \pmod{5}\\ 15w_3 &\equiv 2 \pmod{7}\\ \end{cases} \)
然后发现对于单个同余方程，可以 exgcd 解决。
具体求解步骤
- 计算模数的积 \(M\)
- 计算第 \(i\) 个方程的 \(c_i=\frac{M}{m_i}\)
- 计算 \(c_i\) 在模 \(m_i\) 意义下的逆元 \(c_i^{-1}\)
- \(x=\sum\limits_{i=1}^na_ic_ic_i^{-1}\pmod M\)
证明公式满足
证明 \(x=\sum\limits_{i=1}^na_ic_ic_i^{-1}\pmod M\) 满足每个同余方程
因为模数两两互质，又 \(c_i=\frac{M}{m_i}\)，即除去了 \(m_i\)，即剩下的乘积一定都与 \(m_i\) 互质，所以 \(c_i \perp m_i\)，互质才会有逆元。
当 \(i \neq j\) 时，\(c_j\equiv 0\pmod {m_i}\)，则 \(c_jc_j^{-1}\equiv 0\pmod {m_i}\)
当 \(i = j\) 时，\(c_j\not\equiv 0\pmod {m_i}\)，则 \(c_jc_j^{-1}\equiv 1\pmod {m_i}\)
当公式中的 \(i\ne j\) 的时候，数值都为 \(0\)，都消失了，只留下了 \(i=j\) 时的 \(1\)
故 \(x\equiv\sum\limits_{j=1}^na_jc_jc_j^{-1}\pmod {m_i}\\ \equiv r_ic_ic_i^{-1}\pmod {m_i}\\ \equiv r_i\pmod {m_i}\)
代码+模板题两道
inline ll CRT(ll a[], ll b[], ll n)
{
ll p = 1, x = 0;
for (int i = 0; i < n; ++i)
p *= a[i];
for (int i = 0; i < n; ++i)
{
ll r = p / a[i];
x += (b[i] * r * inv(r, a[i])) % p; // inv函数是求逆元，可以用exgcd实现，注意这里不能用费马小定理呢
}
return x % p;
}
板子，不会的话记下来
模板题，洛谷P1495 曹冲养猪
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll exgcd(ll a, ll b, ll &x, ll &y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
ll d = exgcd(b, a % b, y, x);
y -= (a / b) * x;
return d;
}
inline ll inv(ll a, ll p)
{
ll x, y;
exgcd(a, p, x, y);
return (x % p + p) % p;
}
inline ll CRT(ll a[], ll b[], ll n)
{
ll p = 1, x = 0;
for (int i = 0; i < n; ++i)
p *= a[i];
for (int i = 0; i < n; ++i)
{
ll r = p / a[i];
x += (b[i] * r * inv(r, a[i])) % p;
}
return x % p;
}
int main()
{
ll n, a[10], b[10];
scanf("%lld", &n);
for (int i = 0; i < n; ++i)
scanf("%lld%lld", a + i, b + i);
printf("%lld\n", CRT(a, b, n));
return 0;
}
P3868 [TJOI2009] 猜数字
这道题略加转换就变成了模板题
\(\forall i\in [1,k]\)，有 \(b_i | (n-a_i)\)
根据同余基本性质：
\(n-a_i\equiv 0\pmod {b_i}\)
\(n\equiv a_i\pmod {b_i}\)
用中国剩余定理解就好了，都说了bi两两互质。
#include <bits/stdc++.h>
#define rei register int
#define LL long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define cvar int n, m, T;
#define rep(i, s, n, c) for (register int i = s; i <= n; i+=c)
#define repd(i, s, n, c) for (register int i = s; i >= n; i-=c)
#define CHECK cout<<"WALKED"<<endl;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
#define pb push_back
#define ls id<<1
#define rs id<<1|1
const int INF = INT_MAX;
long long binpow(long long a, long long b, LL mod){long long res = 1; while (b > 0){if (b & 1) res = res * a % mod;a = a * a % mod; b >>= 1; } return res;}
using namespace std;
__int128 read128()
{
__int128 f = 1, w = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch <= '9' && ch >= '0') {
w = (w << 1) + (w << 3) + ch - '0';
ch = getchar();
}
return f * w;
}
void print(__int128 x)
{
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9) print(x / 10);
putchar(x % 10 + '0');
}
__int128 a[20], b[20], M = 1;
int K;
__int128 exgcd(__int128 a, __int128 b, __int128 &x, __int128 &y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
__int128 d = exgcd(b, a % b, y, x);
y -= ( a/ b) * x;
return d;
}
__int128 inv(__int128 a, __int128 mod)
{
__int128 x, y;
exgcd(a, mod, x, y);
return (x % mod + mod) % mod;
}
void crt()
{
__int128 x = 0;
rep (i, 1, K, 1) {
__int128 ri = a[i], ci = M / b[i], ci_inv = inv(ci, b[i]);
x = (x + ri * ci * ci_inv) % M;
}
x %= M;
print(x);
}
int main()
{
cin >> K;
rep (i, 1, K, 1) a[i] = read128();
rep (i, 1, K, 1) b[i] = read128();
rep (i, 1, K, 1) a[i] = (a[i] % b[i] + b[i]) % b[i];
// b[i]互质，crt即可
rep (i, 1, K, 1) M = M * b[i];
crt();
return 0;
}