中国剩余定理 & 扩展

鉴于之前写的中国剩余定理~~依托构思~~，现在重写一篇。

中国剩余定理

中国剩余定理(CRT)可求解如下形式的一元线性同余方程组 \[ \begin{cases} x \equiv a_1\ \pmod{p_1} \\[6pt] x\equiv a_2\ \pmod{p_2} \\[6pt] \quad\vdots \\[6pt] x \equiv a_n\ \pmod{p_k}\end{cases} \] 其中 \(p_1,p_2,\cdots,p_k\) 两两互质。

板子题：P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪

算法原理很简单

计算 \(P = \prod p_i\)
记 \(m_i = \frac{P}{p_i}\) ，\(m_i^{-1}\) 为模 \(p_i\) 意义下的乘法逆元，求 \(c_i = m_im_i^{-1}\)
方程组的唯一解 \(x = \sum_{i=1}^{k}a_ic_i\pmod{P}\)

证明就不讲了，中国剩余定理主要还是流程比较难记（确信）

时间复杂度 \(\mathcal{O}(n \log V)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(15))

int a[N],p[N];
void exgcd(int a, int b, int &x, int &y)
{
	if(!b) { x = 1, y = 0; }
	else exgcd(b, a % b, y, x), y -= a / b * x;
}
int solve(int n, int P)
{
	int res = 0;
	for(int i = 1; i <= n; i++)
	{
		int m = P / p[i], x, y;
		exgcd(m, p[i], x, y); // m * x % p[i] = 1;
		res = (res + a[i] * m % P * x % P) % P;
	}
	return (res % P + P) % P;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	// freopen("check.in","r",stdin);
	// freopen("check.out","w",stdout);
	int n, P = 1; cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> p[i] >> a[i]; P = P * p[i];
	}
	cout << solve(n, P) << '\n';
	return 0;
}

扩展中国剩余定理

ExCRT 用于解决 \(p_i\) 不一定互质的情况

设两个方程为 \(x \equiv a_1 \pmod{p_1},~x \equiv a_2 \pmod{p_2}\) 。

可得 \[ x = p_1\cdot u +a_1 = p_2\cdot v + a_2 \] 因此 \[ p_1 \cdot u - p_2 \cdot v = a_2 - a_1 \] 令 \(c = (a_2 - a_1)\) 。由裴蜀定理，当且仅当 \(\gcd(p_1,p_2)\mid c\) 时有解。

于是我们可以通过 exgcd 求出一对 \(u_1,v_1\) ，满足 \(p_1\cdot u_1 + p_2 \cdot v_1=g\) （\(-p_2\) 与此实际上等价）

令 \(g = \gcd(p_1,p_2)\) ，显然 \(p_1u_1 \cdot \frac{c}{g} + p_2v_1 \cdot \frac{c}{g} = c\) ，则 \[ \begin{cases} u = u_1 \cdot \frac{c}{g} + \frac{p_2}{g}\cdot k \\[8pt]v = v_1 \cdot \frac{c}{g} - \frac{p_1}{g}\cdot k \end{cases} \] 为一组通解。于是我们求最小的解 \(u_0 \equiv u_1 \cdot \frac{c}{g} \pmod{\frac{p_2}{g}}\) ，钦定 \(u_0 > 0\) （都是为了方便和防止溢出）。

那么原方程就可以写作 \[ x \equiv p_1 u_0 + a_1 \pmod{\mathrm{lcm}(p_1,p_2)} \] 这样我们就合并了两个式子，依此类推可以解决所有的式子。

板子题：P4777 【模板】扩展中国剩余定理（EXCRT）

时间复杂度 \(\mathcal{O}(n \log V)\)

代码：

// 2024年02月09日 03:38:48
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))

int exgcd(int a, int b, int &x, int &y)
{
    int d = a;
    if(!b) { x = 1, y = 0; }
    else { d = exgcd(b, a % b, y, x), y -= a / b * x;}
    return d;
}
int a[N], p[N];
int ExCRT(int n)
{
    int u, v, p1 = p[1], res = a[1];
    for(int i = 2; i <= n; i++)
    {
        int p2 = p[i], c = (a[i] - res % p2 + p2) % p2;
        int g = exgcd(p1, p2, u, v); assert(c % g == 0);
        int l = p2 / g; u = (__int128_t) u * (c / g) % l;
        res += u * p1; p1 *= l; res = (res % p1 + p1) % p1;
    }
    return (res % p1 + p1) % p1;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n;
    for(int i = 1; i <= n; i++) cin >> p[i] >> a[i];
    cout << ExCRT(n) << '\n';
    return 0;
}