标签：剩余 le 定理 笔记 times ans ll equiv

作用

中国剩余定理 （Chinese Remainder Theorem, CRT），也称孙子定理，是用来求解线性同余方程组，即如下面的方程组：

\[\begin{cases} x \equiv &a_1\ ({\rm mod}\ p_1) \\ x \equiv &a_2\ ({\rm mod}\ p_2) \\ & \vdots \\ x \equiv &a_n\ ({\rm mod}\ p_n) \end{cases} \]

这个定理可以在 $O(n \log p) $ 的时间内求解这个方程组的最小整数解，要求 \(p_1,p_2,\dots p_n\) 两两互质。

定理

这个定理告诉我们要怎么求解 \(x\) 的最小正整数值。

实现步骤：

1. 设 \(M = \displaystyle\prod_{1 \le i \le n} p_i\)， 求出 \(M\) 。

2. 设 \(m_i = \frac{M}{p_i}\) , \(t_i = m_i^{-1} \pmod {p_i}\) ，求出每个 \(m_i\) 。

3. \(x\) 的一个解是 \(\displaystyle\sum_{1\le i\le n}a_i\times m_i \times t_i\) ，最小的正整数解就是 \(x \bmod M\) 。

证明非常简单，对于任意一个方程 \(x \equiv a_k \pmod {p_k}\) ，除了 \(k\) 以外的所有 \(a_i \times m_i \times m_i^{-1}\) 整除 \(p_k\) ，而 \(a_k \times m_k \times m_k^{-1}\) 在模 \(p_k\) 意义下变为：

\[a_k \times m_k \times m_k^{-1} \equiv a_k \pmod {p_k} \]

得证。

由于求逆元的复杂度是 \(O(\log \sqrt p)\) ( \(\sqrt p\) 是欧拉函数的时间复杂度 )，所以总的时间复杂度是 \(O(n \log p)\) 。

code

int n;
typedef long long ll;
ll p[15] = {0}, a[15] = {0};
ll phi(ll x) {
	ll ans = x;
	for (ll d = 2; x > 1; d++) {
		if (d * d > x)
			return ans / x * (x - 1);
		if (x % d == 0) {
			ans = ans / d * (d - 1);
			while (x % d == 0)
				x /= d;
		}
	}
	return ans;
}
ll fpow(ll a, ll b, ll p) {
	if (b == 0)
		return 1ll;
	ll ans = fpow(a, b / 2, p);
	ans = ans * ans % p;
	if (b % 2 == 1)
		ans = ans * a % p;
	return ans;
}
ll CRT() {
	ll mul = 1;
	for (int i = 1; i <= n; i++)
		mul *= p[i];
	ll ans = 0;
	for (int i = 1; i <= n; i++)
		ans += a[i] * fpow(mul / p[i], phi(p[i]) - 1, p[i]) % mul * (mul / p[i]) % mul, ans %= mul;
	return ans % mul;
}

一些题目

暂时没有。

标签：剩余,le,定理,笔记,times,ans,ll,equiv
From： https://www.cnblogs.com/rlc202204/p/16949465.html