OI 数学学习笔记
001_ 整除
001.1_ 整除基础
001.1A 基本定义
整除与因数倍数的定义： 设 \(a,b \in \mathbb{Z}，b \ne 0\)，若存在 \(q \in \mathbb Z\)，使得 \(a = bq\)，则称 \(b\) 整除 \(a\)， 记为 \(b \mid a\)，此时称 \(a\) 为 \(b\) 的因数，\(b\) 为 \(a\) 的倍数.
带余除法与余数的定义： 设 \(a,b \in \mathbb{Z}，b \ne 0\)，存在唯一的 \(q,r \in \mathbb Z\)，使得 $a = bq + r,0 \leqslant r < |b| $，此时记 \(r\) 为余数，记为 \(\langle a \rangle _{b}\)（无歧义 \(b\) 可省略） 或 \(a \bmod b\).
公因数与最大公因数的定义： 设 \(a_1, a_2, \cdots, a_n\) 为不全为零的整数，如果存在 \(b \in \mathbb Z\)，使得 \(d \mid a_i (i = 1, 2, \cdots ,n)\)，则 \(d\) 叫做 \(a_1, a_2, \cdots, a_n\) 的一个公因数. \(a_1, a_2, \cdots, a_n\) 的公因数中最大的称为最大公因数， 记作 \((a_1, a_2,\cdots a_n)\) 或 \(\gcd(a_1, a_2,\cdots a_n)\). 若 \((a_1, a_2,\cdots a_n) = 1\)，则称 \(a_1, a_2, \cdots, a_n\) 互素.
公倍数与最小公倍数的定义： 设 \(a_1, a_2, \cdots, a_n\) 为全不为零的整数，若 \(a_i \mid m (1 \leqslant i \leqslant n)\)，则 \(m\) 叫做 \(a_1, a_2, \cdots, a_n\) 的一个公倍数. \(a_1, a_2, \cdots, a_n\) 的公倍数中最小的称为最小公倍数， 记作 \([a_1, a_2,\cdots a_n]\).
素数与合数的定义： 设 \(p \in \mathbb Z, \ p > 1\). 如果 \(p\) 正因数只有 \(1\) 和 \(p\)，那么就称 \(p\) 为素数；反之则称 \(p\) 为合数.
001.1B 整除的性质
设 $a,b,c \in \mathbb Z $，则
-
若 \(c \mid b,\ b \mid a\)，则 \(c \mid a\).
-
若 \(b \mid a,\ c \ne 0\)，则 \(bc \mid ac\).
-
若 \(c \mid a,\ c \mid b\)，对于任意 \(m，n \in \mathbb Z\)，都有 \(c \mid ma + nb\).
-
若 \(b \mid a,\ a \mid b\)，则 \(a = \pm b\).
证明方法：将 \(a,b,c\) 替换成 \(q\).
001.1C 余数的性质
设 \(a_1, a_2, b \in \mathbb Z\)，则 (角括号外省略了 \(b\) )
-
\(\langle a_1 + a_2 \rangle = \langle \langle a_1 \rangle + \langle a_2 \rangle \rangle\) .
-
\(\langle a_1 - a_2 \rangle = \langle \langle a_1 \rangle - \langle a_2 \rangle \rangle\) .
-
\(\langle a_1 a_2 \rangle = \langle \langle a_1 \rangle \langle a_2 \rangle \rangle\) .
证明方法：将 \(a_1, a_2 ,b\) 替换成 \(q\).
001.2_ 欧几里得算法
[定理1.2.1（欧几里得定理）] 设 \(a, b, c\) 是不全为零的整数，若存在 \(q \in Z\)， 使得 \(a = bq + c\)， 则 \((a, b) = (b, c)\)，即 \((a + bq, b) = (a,b)\).
证明： 由 \((b, c) \mid b, \ (b, c) \mid c\) 可得 \((b, c) \mid bq + c\) 即 \((b,c) \mid a\)，即 \((b, c)\) 为 \(a, b\) 的公因数，可知 \((b, c) \leqslant (a, b)\)， 同理由 \((a, b) \mid a, \ (a, b) \mid b\) 得到 \((a, b) \mid a - bq\) 即 \((a,b) \mid c\)，可以得出 \((a, b)\) 是 \(b,c\) 的公因数，即有 \((a, b) \leqslant (b, c)\)，从而有 \((a, b) = (b, c)\). \(\Box\)
001.2A 欧几里得算法
欧几里得算法又名辗转相除法，用来求解两数的最大公因数
设整数 \(a > 0, b > 0\). 令 \(r_0 = a, r_1 = b\)，进行带余除法得到:
最后我们可以得到 \((a, b) = r_n\).
这是由于 \((a, b) = (r_0, r_1) = (r_1, r_2) = \dots = (r_{n-1}, r_n) = (r_n, 0) = r_n\) （由 定理1.1 ）
001.2B欧几里得算法的代码实现
数据范围要求：若以 gcd(a, b) 为格式输入，则输入a和b不应当大于 \(10^{10^6}\). 总之大可放心用.
long long gcd(long long a, long long b)
{
if (b == 0) return a;
else return gcd(b, a % b);
}
时间复杂度： 该算法的时间复杂度为 \(\mathrm{O}(\log n)\).
001.3_ 一次不定方程
001.3A 裴蜀定理
[定理1.3.1（裴蜀定理）] 设 \(a, b\) 是不全为零的整数，则 存在 \(s, t \in \mathbb Z\)，使得
\[\boxed{sa + tb = (a, b)}. \]证明： 若 \(a, b\) 有一个为零，则显然定理成立. 首先考虑 \(a > 0\) 且 \(b > 0\) 时，对进行辗转相除法的式子进行变形：
由 \(r_n = r_{n-2} - r_{n-1}q_{n-1}, \ r_{n-1} = r_{n-3} - r_{n-2}q_{n-2}\) 可以得到
\[\begin{aligned} r_n &= r_{n-2} - (r_{n-3} - r_{n-2}q_{n-2})q_{n-1} \\ &= r_{n-2}(1+q_{n-1}q_{n-2}) - r_{n-3}q_{n-1} \tag{1} \end{aligned} \]在这里我们将 \(1 + q_{n-1}q_{n-2}\) 看作常数 \(m\)，又跟据 \(r_{n-2} = r_{n-4} - r_{n-3}q_{n-3}\)得到:
\[\begin{aligned} r_n &= (r_{n-4} - r_{n-3}q_{n-3})m - r_{n-3}q_{n-1} \\ &= r_{n-3}(-q_{n-3}m - q_{n-1}) + r_{n-4}m \end{aligned}\]这样又化为了式 \((1.3.2A)\) 的形式，以此类推，最终我们得到 \(r_n = sr_0 + tr_1\)，从而有 \(sa + tb = (a, b)\). 由于显然有 \((a, b) = (a, -b) = (-a, b)\)，从而 \(a, b\) 不全大于零的情况可化为上述情况，显然成立. \(\Box\)
[定理1.3.2（定理1.3.2的推广）] 设整数 \(a_1, a_2, \cdots, a_n\) 不全为零，则存在 \(s_1, s_2, \cdots, s_n \in \mathbb Z\) 使得
\[\boxed{s_1a_1 + s_2a_2 + \cdots + s_na_n = (a_1, a_2, \cdots, a_n)} \][定理1.3.3]
-
设\(a, b\) 为不全为零的整数，则 \((a, b) = 1 \Longleftrightarrow \exists s, t \in \mathbb Z, \ sa + tb = 1\).
-
设 \(a, b, c \in \mathbb Z\)，则 \((ac, bc) = (a, b)|c|\). (这里根据 \((1.3.2A)\) 式在两边乘 \(2\) 即得)
-
设 \(d \in \mathbb{N}^+\)，则 \(d = (a, b) \Longleftrightarrow \left(\dfrac{a}{d}, \dfrac{b}{d}\right) = 1\).
-
\((a, b) = 1, \ a \mid bc \Rightarrow a \mid c\).
-
\((a, b) = 1, \ a \mid c, \ b \mid c \Rightarrow ab \mid c\).
-
\((a, b) = 1, \ (a, c) = 1 \Rightarrow (a, bc) = 1\).
001.3B 一次不定方程的解
一次不定方程的定义： 设整数 \(k \geqslant 2, \ a_1, a_2, \cdots a_k, c \in \mathbb Z\)，且 \(a_1, a_2, \cdots, a_k\) 均不为零， 未知数 \(x_1, x_2, \cdots, x_k\) 取值均为整数的方程 \(a_1 x_1 + a_2 x_2 + \cdots + a_k x_k = c\) 称为 \(k\) 元一次不定方程.
[定理1.3.4] 设 \(a, b, c \in \mathbb Z\)，\(a, b\) 均不为零，\(d = (a, b)\)，对于二元一次不定方程
\[ax + by = c \]-
二元一次不定方程 \(ax + by = c\) 有解的充要条件是 \(d \mid c\).
-
设 \(x = x_0, \ y = y_0\) 是该不定方程的一组解，则它的所有解可表示为:
特别地，若 \(d = 1\)，代入得到所有解都可表示为 \(x = x_0 + bt, \ y = y_0 + at\).
证明：
-
如果上述方程有整数解，显然有 \((a, b) \mid c\)，即 \(d \mid c\). 同时，由 *定理1.3.1* 可知，存在 \(s, t \in \mathbb Z\)，使得 \(sa + tb = (a, b)\)， 设 \(c = k(a, b), \ k \in \mathbb Z\)，则有 \(ska+tkb = k(a, b) = c\)，此时，方程必有两解：\(sk\) 与 \(tk\).
-
设 \(x, y\) 是方程的任意一组解，有 \(ax + by = c\)，由 \(x_0, y_0\) 是方程的一组解，可得 \(ax_0 + by_0 = c\)，两式相减，得：
由 *定理1.3.3(3)* 可知，\((\dfrac{a}{d}, \dfrac{b}{d}) = 1\)，又由 定理1.4.4 可得 \(\dfrac{a}{d} \mid y_0 - y\)，故而设 \(t \in \mathbb Z\)，有 \(y_0 - y = \dfrac{a}{d}t\)，即 \(y = y_0 - \dfrac{a}{d}t\)，对于任意 \(t\)，都得到对应的 \(y\)，同理此时有 \(x = x_0 +\dfrac{b}{d}t\). 继而该方程的全部解可表示为 \(x = x_0 + \dfrac{b}{d}t, \ y = y_0 - \dfrac{a}{d}t\)的形式，从而得证. \(\Box\)
[定理1.3.5（定理1.3.4的推广）]设 \(k\) 元一次不定方程
\[a_1x_1 + a_2x_2 + \cdots + a_nx_n = c \]有整数解的充要条件是 \(d \mid c\)，其中 \(d = (a_1, a_2, \cdots, a_n)\).
001.3C 拓展欧几里得算法
我们发现，裴蜀定理证明了上述方程有一组根，我们对辗转相除法进行变形，继而就可以求出二元一次不定方程的一组整数解，从而可以求出二元一次不定方程全部整数解的形式.
设整数 \(a > 0, b > 0\). 要求方程 \(ax + by = (a, b)\) 的一组根，我们先考虑方程，根据 定理1.2.1 有:
\[bx_1 + (a \bmod b)y_1 = (b, a \bmod b) = (a, b) \]我们将 \(a \bmod b\) 替换为 \(a - \lfloor \dfrac{a}{b} \rfloor b\)，并带入上述方程：
\[\begin{aligned} bx_1 + (a - \lfloor \dfrac{a}{b} \rfloor b)y_1&= (a, b) \\ ay_1 + bx_1 - b\lfloor \dfrac{a}{b} \rfloor y_1 &= (a, b) \\ ay_1 + b(x_1 - \lfloor \dfrac{a}{b} \rfloor y_1) &= (a, b) \end{aligned}\]可以发现这个式子与原方程形式相同，我们继而令 \(x = y_1, \ y = x_1 - \lfloor \dfrac{a}{b} \rfloor y_1\)，从而递归地进行求解. 而递归到 \(b = 0\) 时，此时有 \(x_1 = 1, y_1 = 0\)，然后返回.
特别地，如果我们求出这个方程的解为 \(x\) 和 \(y\)，根据*定理1.3.4及其证明(1)*，我们依次可以求出方程 \(ax + bx = c, \ (a, b) \mid c\) 的一组特解为
\[x_0 = x\dfrac{c}{(a, b)}, \ y_0 = y\dfrac{c}{(a, b)} \]时间复杂度： 显然这个算法的时间复杂度与辗转相除法相同，为 \(\rm O(\log b)\).
001.3D 拓展欧几里得的代码实现
数据范围要求：若以 Exgcd(a, b) 为格式输入，则输入a和b不应当大于 \(10^{10^6}\). 总之大可放心用.
#define ll long long
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, x, y);
ll t = x;
x = y;
y = t - (a / b) * y;
return d;
}
001.4_ 算术基本定理与素数筛
001.4A 算术基本定理
[定理1.5.1（算术基本定理）] 设整数 \(a > 1\)，则 \(a\) 可唯一地分解为
\[a = p_1p_2 \cdots p_n \]其中 \(p_i(1 \leqslant i \leqslant n)\) 是满足 \(p_1 \leqslant p_2 \leqslant \cdots \leqslant p_n\) 的素数.
证明：这种分解的存在性是易见的，而分解的唯一性可以用反证法证明.
设整数 \(a > 1\)，它的标准分解式为：
\[\boxed{a = p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_k^{\alpha_k}} \]
其中整数 \(\alpha_i > 0(1 \leqslant i \leqslant k), \ p_1 < p_2 < \cdots < p_k\).
001.4B 分解素因数
相当多情况下需要将一个整数 \(n\) 分解成标准分解式的形式，以解决问题；其他的情况只需要得到所有 \(n\) 的素因数，也可应用分解素因数的方法.
方法：对 \(n\) 分解素因数，那么顺序枚举 \(2\) 到 \(\sqrt n\) 的数. 如果这个数 \(i\) 能整除 \(n\)，则将它加入素因数表，并使 \(n\) 不停除以 \(i\) 直到不能整除，记录次数并记入指数表.
证明：首先 \(2\) 和 \(3\) 都是素数. 首先，如果 \(i\) 是合数，那么它的质因数应当小于它，由于是顺序枚举，那么 \(i\) 的所有质因数已被枚举过，枚举过程它的质因数的过程中 \(n\) 已将 \(i\) 的所有质因数除尽，从而 \(i\) 不可能整除 \(n\)，以此类推，在素因数表中的皆为素数. 由于各个素数互质，故而 \(n\) 的所有素因数都能加入素因数表.
时间复杂度：该方法只需要枚举 \(2\) 至 \(\sqrt n\) 的数据，复杂度为 \(\rm O(\sqrt n)\).
001.4C分解素因数的代码实现
数据范围要求：若以 PrimeFactorize(N) 为格式输入，则输入N不应当大于 \(10^{15}\).
#define ll long long // 不开long long见祖宗
#define MAXP 1e5 + 5 // 可调整
#define MAXA 1e5 + 5 // 可调整
ll pi[MAXP], ai[MAXA], k, N;
// pi[i]对应标准分解式的pi，ai[i]对应标准分解式的ai，k是数组下标，N是待分解的数
void PrimeFactorize(ll N)
{
for (int i = 2; i * i <= N; i++)
if (N % i == 0){
pi[++k] = i;
while (N % i == 0){
N /= i;
ai[k]++;
}
}
if (N > 1)
pi[++k] = N, ai[k] = 1;
}
001.5_素数筛
001.4A 埃式筛
判断 \(n\) 以内的素数，较为简便的方式是枚举 \(1\) 至 \(\sqrt{n}\) 以内的所有数，并在枚举时将其所有不超过 \(n\) 的倍数标记掉，显然到最后未被标记的就是素数，这就是埃拉托斯特尼筛法（厄拉多塞筛法），也称埃式筛.
时间复杂度： 埃式筛的时间复杂度是 \(\rm O (n\log \log n)\). 埃式筛的时间复杂度这里不证 （其实是因为我不会doge）
001.5B埃式筛的代码实现
数据范围要求：若以 EratosthenesPrime(n) 为格式输入，则输入n不应当大于 \(1.5 \times 10^8\).
#define ll long long //不开 long long 见祖宗
#define MAXN 1e5 + 10 //可调整
#define MAXP 1e4 + 10 //可调整
ll vis[MAXN], prime[MAXP], n, p = 0;
//n即为素数筛中的n, p是过程中素数的下标, 最后p就是小于n的素数的数量
void EratosthenesPrime(ll N)
{
vis[1] = 1;
for (ll i = 2; i * i <= N; i++)
for (ll j = i, k = i * j; k <= n; j++, k = i * j)
vis[k] = 1; //由于i的1到i - 1倍都遍历过了，所以跳过
for (ll i = 1; i <= N; i++)
if (!vis[i]) prime[++p] = i;
}
001.4C 线性筛
线性筛在此基础上进行了改进，保证每个数都会且仅会被其最小素因数筛到. 首先建立一个空的标记表和素数表，我们考虑每一个正整数 \(a_i (0 \leqslant i \leqslant n)\)，使得 \(a_i \leqslant n\)：
-
若 \(a_i\) 未被标记，说明它是素数，那么我们将它加入素数表中.
-
对于所有枚举到的正整数 \(a_i\)，枚举当前素数表中的所有素数，直到这个素数 \(p_k\) 是 \(a_i\) 的因数. 同时标记 \(a_i \times p_k\).
证明： 如果 \(a_i\) 是素数，那么显然它不会被标记，考虑\(a_i\)为合数的情况：从步骤1中我们可以发现，由于从小到大枚举 \(a_i\)，故而加入素数表的素数是单调递增的，从而在步骤2中枚举到的最后的素数 \(p_k\)，是 \(a_i\) 的最小素因数. 从而我们设这个正整数 \(a_i\) 的标准分解式为： \(a_i = p_1^{\alpha_1}p_2^{\alpha_12} \cdots p_q^{\alpha_q}\)，从而 \(p_1 = p_k\).
在枚举到 \(a_i\) 之前，已经枚举过数 \(a_s = p_1^{\alpha_1 - 1}p_2^{\alpha_2} \cdots p_q^{\alpha _q}\)，这个数的最小素因数是 \(p_1\)，那么在这个数 \(a_s\) 在遍历到 \(p_1\) 的时候，就标记了 \(a_i\)，这说明 \(a_i\) 会被标记. 显然它不会被 \(a_t = p_1^{\alpha_1}p_2^{\alpha_2 - 1} \cdots p_q^{\alpha_q}\) 之类的数标记，这是因为 \(a_t\) 在遍历到最小素因数 \(p_1\) 时就停止了遍历素数表，继而不会标记比它更大的素因数\(p_2, \ p_3\). 从而 \(a_i\) 会且仅会被 \(a_s\) 标记. \(\Box\)
时间复杂度： 由于每个数都会且仅会被枚举和标记一次，故而总的渐进时间复杂度为 \(\rm O (n)\).
001.5D线性筛的代码实现
数据范围要求：若以 EulerPrime(n) 为格式输入，则输入n不应当大于 \(5 \times 10^8\).
#define ll long long //不开 long long 见祖宗
#define MAXN 1e5 + 10 //可调整
#define MAXP 1e4 + 10 //可调整
ll vis[MAXN], prime[MAXP], N, p = 0;
//n即为素数筛中的n, p是过程中素数的下标, 最后p就是小于n的素数的数量
void EulerPrime(ll N )
{
for (ll i = 2; i <= N; i++){
if (!vis[i]) prime[++p] = i;
for (ll j = 1; j <= p && i * prime[j] <= N; j++){
vis[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
}
002_ 同余
002.1_ 同余基础
002.1A 同余的定义
设 \(a, b \in \mathbb Z\)，\(m\) 是一个正整数，如果用 \(m\) 分别去除 \(a\)， \(b\)，所得的余数相同，则称 \(a\) 和 \(b\) 关于模 \(m\) 同余，用符号 \(a \equiv b \pmod m\) 表示；如果余数不同，那么称 \(a\) 和 \(b\) 关于模 \(m\) 不同余，用符号 \(a \not\equiv b \pmod m\) 表示.
C++中的负数取余：如果运算过程中需要负数 n 需要对 m 取余，那么应当写为
ll MOD(ll n, ll m)
{
return (n % m + m) % m;
}
[同余的充要条件] 如果 \(a \equiv b \pmod m\)，替换成带余除法的形式，较为简单得：存在 \(t \in \mathbb Z\)，使得 \(a - mt = b\) 即 \(a - b = mt\)，从而 \(m \mid a - b\). 故而我们得到 \(a \equiv b \pmod m\) 的充要条件是 \(m \mid a - b\).
我们易于得到：
-
\(a \equiv a \pmod m\)
-
\(a \equiv b \pmod m \Longrightarrow b \equiv a \pmod m\)
-
\(a \equiv b \pmod m, \ b \equiv c \pmod m \Longrightarrow a \equiv c \pmod m\)
002.1B 同余的算术性质
[定理2.1.1] 设 \(a, b, c, d \in \mathbb Z\)，\(m\) 是任意正整数.
-
如果 \(a \equiv b \pmod m\)，那么 \(ac \equiv bc \pmod m\).
-
如果 \(a \equiv b \pmod m, \ c \equiv d \pmod m\)，那么 \(a + c \equiv b + d \pmod m\).
-
如果 \(a \equiv b \pmod m, \ c \equiv d \pmod m\)，那么 \(ac \equiv bd \pmod m\). (注意这里只有充分性，没有必要性)
-
如果 \(a \equiv b \pmod m\)，那么对于任意正整数 \(n\)，有 \(a^n \equiv b^n \pmod m\).
我们从同余的上述基本算术基本定理容易得到
如果 \(a \equiv b \pmod m\)，那么对于任意整系数多项式 \(f(x) = r_kx^k + \cdots + r_1x + r_0, \ r_i \in \mathbb Z, \ 0 \leqslant i \leqslant k\)，有 \(f(a) = f(b)\).
证明：
-
如果 \(a \equiv b \pmod m\)，则有 \(m \mid a - b\)，从而有 \(m \mid ac - bc\)，所以 \(ac \equiv bc \pmod m\).
-
由 \(a \equiv b \pmod m, \ c \equiv d \pmod m\) 可知 \(m \mid a - b, \ m \mid c - d\)，所以有 \(m \mid (a - b) + (c - d)\) 即 \(m \mid (a + c) - (b + d)\)，可以推出 \(a + c \equiv b + d \pmod m\).
-
由题设可知 \(m \mid a - b, \ m \mid c - d\)，则 \(m \mid c(a - b) + b(c - d)\)，即 \(m \mid ac + bd\)，从而有 \(ac \equiv bd \pmod m\).
-
当 \(n\) 为 \(1\) 时，结论显然成立. 假设结论对 \(k (\geqslant 1)\) 也成立，即 \(a^k \equiv b^k \pmod m\). 则当 \(n = k + 1\) 时，又因为 \(a \equiv b \pmod m\)，由 3 可知 \(aa^k \equiv bb^k \pmod m\)，即 \(a^{k + 1} \equiv b^{k + 1} \pmod m\)，从而根据数学归纳法，对于任意正整数 \(n\)，都有 \(a^n \equiv b^n \pmod m\). \(\Box\)
[定理2.1.2] 设 \(a, b, c, d \in \mathbb Z\)，\(m\) 是任意正整数.
-
如果 \(a \equiv b \pmod m\)，正整数 \(d \mid m\)，那么 \(a \equiv b \pmod d\).
-
如果 \(ac \equiv bc \pmod m\)，则 \(a \equiv b \pmod{\dfrac{m}{(c,m)}}\). 特别地，如果 \((c, m) = 1\)，则 \(a \equiv b \pmod m\).
证明:
-
\(a \equiv b \pmod m \Longrightarrow m \mid a - b\)，又\(d \mid m \Longrightarrow d \mid a - b \Longrightarrow a \equiv b \pmod d\).
-
令 \(d = (c, m)\), 由 \(ac \equiv bc \pmod m\) 知，存在 \(k \in \mathbb Z\)，使得 \(ac - bc = km\)，于是有 \((a - c)\dfrac{c}{d} = k\dfrac{m}{d}\) 即 \(\dfrac{m}{d} \mid (a - b)\dfrac{c}{d}\). 又因为 \(d = (c, m)\)，所以 \(\left(\dfrac{c}{d}, \dfrac{m}{d}\right) = 1\)，从而有 \(\dfrac{m}{d} \mid a - b\)，即证得 \(a \equiv b \pmod{\dfrac{m}{d}}\). \(\Box\)
我们对于模 \(m\) 的定理还有两个，有助于解决涉及模 \(m\) 的运算问题.
[定理2.1.3]
-
如果 \(a \equiv b \pmod m\)，又 \(a \equiv b \pmod n\)，那么 \(a \equiv b \pmod{[m, n]}\).
-
如果 \((m, n) = 1\)，那么
证明：
-
由 \(a \equiv b \pmod m\)，\(a \equiv b \pmod n\)，可得 \(m \mid a - b, \ n \mid a - b\)，可知 \(a, b\) 是 \(m, n\) 的公倍数，从而有 \([m, n] \mid a - b\) 即 \(a \equiv b \pmod{[m, n]}\).
-
由于 \((m, n) = 1\)，所以我们有 \([m, n] = mn\)，由1，该定理的充分性可证；显然有 \(m \mid mn, \ n \mid mn\)，从而必要性也可证得. \(\Box\)
002.2_ 剩余系
002.2A 完全剩余系和既约剩余系
我们可以发现，\(\mathbb Z\) 中的元素关于模 \(m\) 总共有 \(m\) 种余数的情况. 换言之，我们可将 \(\mathbb Z\) 中的元素分成 \(m\) 个集合，每个集合中的元素都关于模 \(m\) 同余. 我们将划分出的这些集合叫做等价类.
较为简单地，我们只需要从上述 \(m\) 个集合中选取 \(1\) 个元素讨论，我们便选取 \(m\) 个元素，使其构成一个集合 \(S\)，使得 \(\mathbb Z\) 中的每个元素都与且仅与 \(S\) 中的一个元素同余. 这便引出了剩余系的定义：
剩余系的定义: 设 \(S \subseteq \mathbb Z\)，如果任意整数都与 \(S\) 中的正好一个元素关于模 \(m\) 同余，则称 \(S\) 是模 \(m\) 的一个完全剩余系（简称剩余系），如果 $S = { 0, 1, 2, \cdots, m - 1} $ 则称 \(S\) 是关于模 \(m\) 的标准剩余系或最小非负剩余系.
[定理2.2.1] 设 \(S = \{ a_1, a_2, \cdots, a_k \} \subseteq \mathbb Z\)，则 \(S\) 是模 \(m\) 的一个完全剩余系的充要条件是： \(k = m, \ a_i \not\equiv a_j \pmod m (i \ne j)\).
这个定理根据定义易于理解，在此不做证明.
[定理2.2.2] 设 \(S = \{ a_1, a_2, \cdots, a_m \}\) 是模 \(m\) 的一个完全剩余系，\((k, m) = 1\)，则 \(S' = \{ ka_1 + b, ka_2 + b, \cdots, ka_m + b \}\) 也是模 \(m\) 的一个完全剩余系.
证明： 不妨假设 \(ka_i + b \equiv ka_j + b \pmod m (i \ne j)\)，则由*定理2.1.1(2)*有 \(ka_i \equiv ka_j \pmod m\)，又因为 \((k, m) = 10\)，由*定理2.1.2(2)*可知 \(a_i \equiv a_j \pmod m\)，但根据*定理2.2.1*，这与 \(S\) 是模 \(m\) 的一个完全剩余系相矛盾，继而 \(ka_i + b \not\equiv ka_j + b \pmod m (i \ne j)\)，即 \(S'\) 也是模 \(m\) 的完全剩余系. \(\Box\)
既约剩余系的定义： 在模 \(m\) 的一个完全剩余系 \(S\) 中，有的数与 \(m\) 互素，与 \(m\) 互素的数构成的集合称作模 \(m\) 的一个既约剩余系.
我们设对于模 \(m\) 所划分出的等价类中的一个为 \(S_{[r]} = \{ \cdots,r -m, r, r + m, r + 2m \cdots \}\)，则如果 \((r, m) = 1\) 的话，根据 定理1.2.1 我们得到 \((r - m, m) = (r + m, m) = (r, m) = 1\)，以此类推，该等价类中的所有元素都与 \(m\) 互素；反之，若 \((r, m) \ne 1\)，同理该等价类中的所有元素都与 \(m\) 不互素. 由于模 \(m\) 的完全剩余系中的元素是从各个等价类中选取一个组成的，故而完全剩余系中与 \(m\) 互素的的个数根据等价类是固定的. 即既约剩余系的大小固定.
欧拉函数的定义： 据此，我们定义欧拉函数 \(\varphi(m)\)，表示模 \(m\) 的既约剩余系的大小. 若考虑模 \(m\) 的一个标准剩余系，则 $\varphi (m) $表示不大于 \(m\) 的正整数中与 \(m\) 互素的数的个数.
显然，一个素数与所有小于它的正整数互素，设 \(p\) 为一个素数，则有 \(\varphi(p) = p - 1\). 从而对于任意正整数 \(m\)，都有 \(\varphi(m) \leqslant m - 1\).
[定理2.2.3] 设 \(S = \{ a_1, a_2, \cdots, a_k\} \subseteq \mathbb Z\)，则 \(S\) 是 \(m\) 的一个既约剩余系的充要条件是：
-
\(k = \varphi (m)\)；
-
当 \(i \ne j\) 时， \(a_i \not \equiv a_j \pmod m\)；
-
对任意 \(a_i \in S\)，都有 \((a_i, m) = 1\).
即：任意 \(\varphi(m)\) 个与 \(m\) 互素且两两关于模 \(m\) 不同余的数构成模 \(m\) 的一个既约剩余系.
这个定理通过定义易于证明，其实是我不想写了.
[定理2.2.4] 设 \(S = \{ a_1, a_2, \cdots, a_{\varphi(m)} \}\) 是模 \(m\) 的一个既约剩余系，\((k, m) = 1\)，则 \(S' = \{ka_1, ka_2, \cdots, ka_{\varphi(m)} \}\) 也是模 \(m\) 的一个既约剩余系.
证明： 易证 \(ka_i \not \equiv ka_j \pmod m\)，而对于任意 \(ka_i \in S'\)，因 \((k, m) = 1\)，就有 \((ka_i, m) = (a_i, m) = 1\)，从而由*定理2.2.3*，定理得证. \(\Box\)
002.2B 欧拉定理、费马小定理、威尔逊定理
[定理2.2.5（欧拉定理）] 设 \(a \in \mathbb Z\)，\(m\) 是正整数，如果 \((a, m) = 1\) 那么
\[\boxed{a^{\varphi(m)} \equiv 1 \pmod m} . \]证明： 设 \(S = \{ a_1, a_2, \cdots, a_{\varphi(m)} \}\) 是模 \(m\) 的一个既约剩余系，则由定理2.2.4， $S' = { aa_1, aa_2, \cdots, aa_{\varphi(m)} } $ 也是模 \(m\) 的一个既约剩余系，所以 \(S'\) 中任一数必与 \(S\) 中某个数关于模 \(m\) 同余，且它们一一对应，从而在整体上看，根据定理2.1.1(3)，各个集合内的元素乘积同余，即：
\[a^{\varphi(m)}\prod\limits_{i = 1}^{\varphi(m)}a_i = \prod\limits_{i = 1}^{\varphi(m)}(aa_i) \equiv \prod\limits_{i = 1}^{\varphi(m)}a_i \pmod m . \]根据同余的充要条件，我们得到
\[m \mid a^{\varphi(m)} \cdot \prod\limits_{i = 1}^{\varphi(m)}a_i - \prod\limits_{i = 1}^{\varphi(m)}a_i \ \ \Longleftrightarrow \ \ m \mid (a^{\varphi(m)} - 1) \cdot \prod\limits_{i = 1}^{\varphi(m)}a_i \]由既约剩余系的定义可知，对所有 \(1 \leqslant i \leqslant \varphi(m)\)，都有 \((a_i, m) = 1\)，所以 \((\prod\limits_{i = 1}^{\varphi(m)}a_i,\ m) = 1\)，由上式得 \(m \mid a^{\varphi(m)} - 1\)，即 \(a^{\varphi(m)} \equiv 1 \pmod m\). \(\Box\)
[定理2.2.6（费马小定理）] 如果 \(a \in \mathbb Z\)，\(p\) 为素数，则
\[\boxed{a^p \equiv a \pmod p}. \]特别地，若 \(p \nmid a\)，则
\[\boxed{a^{p - 1} \equiv 1 \pmod p}. \]证明： 若 \(p \nmid a\)，又因 \(p\) 为素数，则 \((a, p) = 1\)，还有 \(\varphi(p) = p - 1\)，由欧拉定理，则易证 \(a^{p - 1} \equiv 1 \pmod p\)，同乘 \(a\)，则证有 \(a^p \equiv a \pmod p\)；若 \(p \mid a\)，则有 \(a^p \equiv a \equiv 0 \pmod p\)，此时定理显然成立. \(\Box\).
002.2C 欧拉函数
002.3_ 乘法逆元
002.3A 线性同余方程
线性同余方程：对于 \(a, b, m \in \mathbb Z\)，\(m > 0\) 且 \(m \nmid a\)，则方程 \(ax \equiv b \pmod m\) 称为线性同余方程的一般形式. 如果有 \(ax_0 \equiv b \pmod m\)，则称 \(x \equiv x_0 \pmod m\) 是该同余方程的一个解.
我们根据 *同余的等价形式*，事实上， \(ax \equiv b \pmod m \Leftrightarrow m \mid ax - b\)，即存在 \(k \in \mathbb Z\)，使得 \(ax - mk = b\)，这里 \(k\) 的符号可以忽略，我们设 \(d = (a, m)\)，继而我们将该同余方程转换为了一个一次不定方程：
\[ax - mk = b \]根据 *定理1.4.1*，该方程有解的充要条件是 \(d \mid b\)，设这个方程的一组解是 \(x_0, k_0\) 而且它的所有解都可表示为：
\[x = x_0 + \dfrac{m}{d}t, \ k = k_0 - \dfrac{a}{d}t \][定理2.3.1] 线性同余方程 \(ax \equiv b \pmod m\)，设 \((a, m) = d\)，则同余方程有解的充要条件是 \(d | b\)，而且线性同余方程的解可表示为：
\[x \equiv x_0 + \dfrac{m}{d}t \pmod m, \quad t = 0, 1, \cdots, d - 1 \]证明：下面要证明该方程有 \(d\) 个解，且满足条件的 \(t = 0, 1, \cdots, d - 1\). 事实上我们就是要从它的解的表示形式中筛出同余的各项. 不妨设 \(x_0 + \dfrac{m}{d}t_1 \equiv x_0 + \dfrac{m}{d}t_2 \pmod m\)，则根据 *定理2.1.1*可作如下变换：
\[x_0 + \dfrac{m}{d}t_1 \equiv x_0 + \dfrac{m}{d}t_2 \pmod m \Longleftrightarrow \dfrac{t_1 - t_2}{d}m \equiv 0 \pmod m \\ \Longleftrightarrow d \mid t_1 - t_2 \Longleftrightarrow t_1 \equiv t_2 \pmod d \]由于线性同余方程和一次不定方程是完全等价的，我们同样可以使用 *拓展欧几里得算法* 进行求解，代码与拓展欧几里得相同.
002.3B 乘法逆元
考虑整数域上关于模 \(m\) 的乘法运算构成了一个交换群 \(Z\)，对于任意 \(a \in Z\)，显然有 \(a \cdot 1 \equiv 1 \cdot a \equiv a \pmod m\)，故而 \(1\) 是 \(Z\) 的单位元.
乘法逆元：那么相应的，根据逆元的定义，存在 \(x \in Z\)，使得 \(ax \equiv 1 \pmod m\)，则 \(x\) 就是 \(a\) 关于模 \(m\) 的乘法逆元，也记为 \(a^{-1}\).
事实上我们发现，这个式子就是线性同余方程的特殊形式，那么同样地，\(x\) 存在逆元的充要条件是 \((a, m) \mid 1\)，即 \((a, m) = 1\).
乘法逆元用于求模意义下的除法：乘法逆元可以用于将除法取模转换为乘法取模，特别地，它能解决一些无法整除情形.
[定理2.3.2] 对于模 \(m\) 下存在乘法逆元的 \(a\)，我们有：
\[\dfrac{b}{a} \equiv ba^{-1} \pmod m. \]证明：我们设 \(\dfrac{b}{a} \equiv k \pmod m\)，我们有
\[\dfrac{b}{a} \equiv k \pmod m \Longleftrightarrow b \equiv ka \pmod m \Longleftrightarrow ba^{-1} \equiv kaa^{-1} \equiv k \pmod m \]从而我们得证 \(\dfrac{b}{a} \equiv ba^{-1} \equiv k \pmod m. \Box\)
求解乘法逆元
拓欧法：一般地，我们将求乘法逆元看作求解线性同余方程，根据上文内容，使用拓展欧几里得法即可.
费马小定理法：对于 \(ax \equiv 1 \pmod p\)，易知有 \(p \nmid a\)，如果 \(p\) 是一个素数，那么依据 *费马小定理* 我们有
\[ax \equiv 1 \equiv a^{p - 1} \pmod p $$故我们仅需使用快速幂求出 $a^{p - 2}$，即得到了 $a$ 的乘法逆元. **线性法**：如果需要求 $1, 2, \cdots, n$ 关于素数 $p$ （这里保证了每个数都存在逆元）每个数的逆元，我们考虑递推实现：$i^{-1} = -k \times j^{-1}$，其中 $j = p \bmod i$，$k = \lfloor \dfrac{p}{i} \rfloor$ **线性法的证明**：易知 $1^{-1} \equiv 1 \pmod p$；对于之后的数 $i$，我们将 $p \bmod i $ 改写成带余除法的式子 $$\begin{aligned}&ki + j = p, \ j < |i| \\ &\Rightarrow ki + j \equiv 0 \pmod p \\ &\Rightarrow ki \cdot i^{-1}j^{-1} + j \cdot i^{-1}j^{-1} \equiv 0 \pmod p\\ &\Rightarrow kj^{-1} + i^{-1} \equiv 0 \pmod p \\ &\Rightarrow i^{-1} \equiv -kj^{-1} \pmod p \ \ \ \ \Box\end{aligned}\]002.3C 求解乘法逆元的代码实现
求解单个数的乘法逆元：使用拓展欧几里得算法，代码参考*拓欧代码*.
求解1~n的关于模素数下的乘法逆元：时间复杂度 \(\rm O(n)\).
数据范围要求：当以 INVn(int n) 为格式输入时，n 不应当大于 \(5 \times 10^8\).
void INVn(int n, int inv[])
{
inv[1] = 1;
for(int i = 2; i <= n; i++)
inv[i] = (p - p / i) * inv[p % i] % p;
}
002.4_ 欧拉函数
002.4A 欧拉函数性质
前面我们通过剩余系对欧拉函数进行了定义，我们接下来研究它的性质.
[定理2.4.1（欧拉函数的计算式）] 我们设 \(m\) 的标准分解式为 \(m = p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_k^{\alpha_k}\)，\(p\) 为质数，则：
\[\boxed{\varphi(m) = m\left(1 - \dfrac{1}{p_1}\right)\left(1 - \dfrac{1}{p_2}\right) \cdots \left(1 - \dfrac{1}{p_k}\right) = m \times \prod\limits_{p \mid m}\left(1 - \dfrac{1}{p}\right) = m \times \prod\limits_{p \mid m}\left(\dfrac{p - 1}{p}\right)}. \]证明： 已知对于任意 \(p_i\)，都有 \(p_i, \ 2p_i, \ \cdots, \ \dfrac{m}{p_i}p_i\)，共 \(\dfrac{m}{p_i}\) 个数与 \(m\) 不互质，我们设这些数的集合为 \(P_i\)，我们设集合 \(M\) 为小于等于 \(m\) 的正整数集，则易知
\[\varphi(m) = \left| M \right| - \left| \bigcup\limits_{i = 1}^{k} P_k \right| \]我们易于知道，\(P_i \cap P_j = \dfrac{m}{p_ip_j}\). 同理对于任意 \(t \leqslant k, \ 1 \leqslant a_i \leqslant t\)，都有:
\[| P_{a_1} \cap P_{a_2} \cap \cdots \cap P_{a_t}| = \dfrac{m}{\prod p_{a_i}} \]根据 容斥原理（将会在后面的部分介绍） 和上式我们得到：
\[\begin{aligned} LHS =& \left| M \right| - \left| \bigcup\limits_{i = 1}^{k} P_i \right| \\ =& \left| M \right| - \sum |P_i| + \sum\limits_{i < j} |P_i \cap P_j| - \sum\limits_{i < j < k} |P_i \cap P_j \cap P_k| \\ &+ \cdots + (-1)^{k - 1}|P_1 \cap P_2 \cap \cdots \cap P_k| \\ =& m - \sum \dfrac{m}{p_i} + \sum\limits_{i < j}\dfrac{m}{p_ip_j} - \sum\limits_{i < j < k}\dfrac{m}{p_ip_jp_k} + \cdots + (-1)^k\dfrac{m}{p_1p_2 \cdots p_k} \\ =& m\left(1 - \dfrac{1}{p_1}\right)\left(1 - \dfrac{1}{p_2}\right) \cdots \left(1 - \dfrac{1}{p_k}\right) = RHS \\ \Box \end{aligned}\][定理2.4.2]
-
如果 \(p\) 是素数且 \(\alpha \geqslant 1\)，则 $$\boxed{\varphi(p^{\alpha}) = p^{\alpha} - p^{\alpha - 1}}.$$
-
设 \((a, b) = d\)，则 $$\boxed{\varphi(ab) = \varphi(a)\varphi(b)\dfrac{d}{\varphi(d)}}$$
-
如果 \((a, b) = 1\)，那么 $$\boxed{\varphi(ab) = \varphi(a)\varphi(b)}.$$
-
如果 \(a \mid b\)，那么 \(\varphi(a) | \varphi(b)\)
证明：
-
考虑模 \(p^\alpha\) 的完全剩余系 \(S = {1, 2, \cdots}\)，在 \(S\) 中与 \(p^\alpha\) 不互素的仅有 \(p\) 的倍数共 \(p^{\alpha - 1}\) 个，显然模 \(p\) 的既约剩余系的个数是 \(p^\alpha - p^{\alpha - 1}\) 个，从而得证.
- \[LHS = ab \cdot \prod \limits_{p \mid ab} \left(1 - \dfrac{1}{p}\right) = \dfrac{ a \prod \limits_{p \mid a} \left(1 - \dfrac{1}{p}\right) \cdot b\prod \limits_{p \mid a} \left(1 - \dfrac{1}{p}\right) \cdot d} {d \prod \limits_{p \mid (a,b)} \left(1 - \dfrac{1}{p}\right)} = \dfrac{d \cdot \varphi(a)\cdot \varphi(b)}{\varphi(d)} = RHS \]
-
显然是2的特殊形式，将 \(d = \varphi(d) = (a, b) = 1\) 带入即可.
[定理2.4.3] 设 \(m\) 是正整数，则
\[\boxed{\sum\limits_{d|m}\varphi(d) = m}. \]证明：
首先，对于素数 \(p\), 和正整数 \(\alpha \geqslant 1\)，考虑 \(a = p^{\alpha}\). 易知 \(a\) 的全部因数可且仅可表示为 \(p^0, p^1, p^2, \cdots, p^{\alpha}\)，根据 3.2.2(1)，这些因数的欧拉函数值之和可表示为：
考虑 \(m\) 的标准分解式 \(m = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}\). 显然，任意 \(d \mid m\) 都可表示为
\[\prod\limits_{\substack{i = 1 \\ 0 \leqslant \beta_i \leqslant \alpha_i}}^k p_i^{\beta_i} \]这里我们便可有序地枚举对于 \(p_i\)，所有\(\beta_i\)的情况，得到所有 \(d \mid m\). 它们的欧拉函数值之和从而可表示为
\[\sum\limits_{d|m}\varphi(d) = \sum\limits_{\beta_1 = 0}^{\alpha_1}\sum\limits_{\beta_2 = 0}^{\alpha_2} \cdots \sum\limits_{\beta_k = 0}^{\alpha_k}\varphi(p_1^{\beta_1}p_2^{\beta_2} \cdots p_k^{\beta_k}) \]由于任意 \(p_i^{\beta_i}\) 间都两两互素，根据 定理3.2.2（3），再将式 \((A)\) 式代入，从而有：
\[\begin{aligned} \sum\limits_{d|m}\varphi(d) &= \sum\limits_{\beta_1 = 0}^{\alpha_1}\sum\limits_{\beta_2 = 0}^{\alpha_2} \cdots \sum\limits_{\beta_k = 0}^{\alpha_k} \varphi(p_1^{\beta_1}) \varphi(p_2^{\beta_2}) \cdots \varphi(p_k^{\beta_k}) \\ &= \sum\limits_{\beta_1 = 0}^{\alpha_1}\varphi(p_1^{\beta_1})\sum\limits_{\beta_2 = 0}^{\alpha_2}\varphi(p_2^{\beta_2}) \cdots \sum\limits_{\beta_k = 0}^{\alpha_k}\varphi(p_k^{\beta_k}) \\ &= p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k} \\ &= m\\ && \Box \end{aligned}\]002.4B 线性筛求欧拉函数
如果要求多个数的欧拉函数值，观察线性筛素数的过程，我们改进并用它求欧拉函数.
方法：在线性筛素数的基础上增加以下细节：考虑 \(a_i\)
-
如果 \(a_i\) 是素数，将记录为 \(\varphi(a_i) = a_i - 1\).
-
仿照线性筛顺序枚举素数表时，枚举到素数 \(p_i\) 时，在进行标记的同时进行以下操作：
(1). 如果 \(p_i \nmid a_i\)，则记录 \(\varphi(a_i \times p_i) = \varphi(a_i) \times (p_i - 1)\);
(2). 如果 \(p_i \mid a_i\)，则记录 \(\varphi(a_i \times p_i) = \varphi(a_i) \times p_1\)；
证明：我们设 \(a_i\) 的标准分解式为 \(a_i = p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_k^{\alpha_k}\). 首先步骤1易证. 其次证明步骤2：
- 如果 \(p_i \nmid a_i\) 的话，由于 \(p_i\) 是素数，那么它们互素，则根据 *定理2.1.2(2)* 可知：
- 如果 \(p_i \mid a_i\) 的话，则易知 \(p_i\) 为 \(a_i\) 的最小素因数，那么被标记的 \(a_i \times p_i\) 与 \(a_i\) 有同样的素因数，根据 *定理2.4.1* 易知
时间复杂度：显然，该算法与线性筛算法时间复杂度相同，为 \(\rm O(n)\).
002.4C 线性求欧拉的代码实现
数据范围要求：如果输入格式为EulerPhi(n)，则n不应当大于 \(5 \times 10^8\).
#define ll long long //不开 long long 见祖宗
#define MAXN 1e5 + 10 //可调整
#define MAXP 1e4 + 10 //可调整
#define MAXF 1e5 + 10 //可调整
ll vis[MAXN], prime[MAXP], phi[MAXF], N, p = 0;
//n即为素数筛中的n, p是过程中素数的下标, phi[i]是i的欧拉函数
void EulerPhi(ll N)
{
for (ll i = 2; i <= N; i++){
if (!vis[i]) {
prime[++p] = i;
phi[i] = i - 1;
}
for (ll j = 1; j <= p && i * prime[j] <= N; j++){
vis[i * prime[j]] = 1;
if (i % phi[j])
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
else {
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
}
}
}
002.4D 分解求欧拉函数及其代码
求单个数的素因数，直接在素因数分解的同时用 *定理2.2.1* 带入即可.
时间复杂度：时间复杂度显然与分解素因数相同，为 \(\rm O(\sqrt n)\).
数据范围要求：如果输入格式为SingleEuler(n)，那么n不应当大于 \(10^{15}\).
#define ll long long // 不开long long见祖宗
ll N, ans;
// N是代求欧拉函数的变量，得到ans就是最后的结果
void SinglePhi(ll N)
{
ans = N;
for (int i = 2; i * i <= N; i++)
if (N % i == 0){
ans = ans / i * (i - 1); //公式中是 ans * (i - 1) / i，但先乘后除见祖宗（
while (N % i == 0) N /= i;
}
if (N > 1)
ans = ans / n * (n - 1);
}
002.5_ 同余方程
002.5A 中国剩余定理
我们定义一个线性同余方程组
\[\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_1, m_2, \cdots, m_k\) 两两互素，我们能够得到：
[定理2.5.1（中国剩余定理）] 定义 \(m = \prod {m_i}，\ M_i = m / m_i， \ N_i \equiv M_i^{-1} \pmod {m_i}\)，则上述方程存在唯一解：
\[\boxed{x \equiv \sum \limits_{i = 1}^{k} a_iM_iN_i \pmod m}. \]证明： 因为对 \(\forall i,j\) 都有 \((m_i, m_j) = 1\)，所以 \((m_i, m / m_i) = 1\) 即 \((M_i, m_i) = 1\)，故逆元 \(N_i\) 总存在。所以对 \(\forall j\)：
\[\sum \limits a_iM_iN_i \equiv a_jM_jN_j + \sum\limits_{i \ne j} a_iM_iN_i \pmod {m_i} \]由于后一项中 \(M_i \equiv 0 \pmod {m_j}\)，故后一项为零，我们立刻得到
\[\sum \limits a_iM_iN_i \equiv a_jM_jN_j \equiv a_j \times 1 \equiv a_j \pmod {m_i} \quad \Box \]002.5B 中国剩余定理的代码实现
复杂度瓶颈在于求解乘法逆元, 时间复杂度 \(O(n \log n)\).
long long getNi(long long p, long long q)
{
long long x = 0, y = 0;
exgcd(p, q, x, y);
return x * p;
}
long long CRT(int n, int ai[], int mi[])
long long ans = 0;
for(int i = 1; i <= n; i++) M *= mi[i];
for(int i = 1; i <= n; i++)
ans = ans + (ai[i] * getNi(M / mi[i], mi[i]) % M + M) % M;
return ans % M
}
002.5C 多项式同余方程及其定理
我们考虑一个多项式同余方程
\[f(x) = a_nx^n + a_{n - 1}x^{n - 1}+\cdots + a_1x_1 + a_0 \equiv 0 \pmod m \]这里限定 \(m\) 为一个素数，事实上，若 \(m\) 不为素数，那么我们考虑它的标准分解式 \(m = p_1^{\alpha _1}p_2^{\alpha _2}\cdots p_k^{\alpha _k}\)，则
\[f(x) \equiv 0 \pmod m \Longleftrightarrow \begin{cases} f(x) \equiv& 0 \pmod{p_1^{\alpha_1}} \\ f(x) \equiv& 0 \pmod{p_2^{\alpha_2}} \\ &\vdots \\ f(x) \equiv& 0 \pmod{p_k^{\alpha_k}} \end{cases} \][定理2.5.2（拉格朗日定理）] 设 \(p\) 为不整除 \(a_n\) 的素数，则同余方程
\[f(x) = a_nx^n + a_{n - 1}x^{n - 1}+\cdots + a_1x_1 + a_0 \equiv 0 \pmod p $$ 至多有 $n$ 解. ----- [**定理2.5.3（威尔逊定理）**] $p$ 为素数的 **当且仅当** \]\boxed{(p - 1)! \equiv -1 \pmod p}.
\[ **证明：** 先证充分性：假设 $p$ 不是素数，则它必有小于 $p$ 的素因数 $a，b$，所以 \](p - 1)! = (p - 1) \times \cdots \times a \times b \times \cdots 1\equiv (p - 1) \times \cdots \times p \times\cdots 1 \not \equiv 0 \equiv -1 \pmod p
\[ 矛盾！故当 $(p - 1)! \equiv -1 \pmod p$ 时， $p$ 为素数. 再证必要性：已知 $p$ 是素数，由费马小定理可知 $x \equiv 1, 2, \cdots, p - 1 \pmod p$ 都为方程 $x^{p - 1} \equiv 0 \pmod m$ 的解，故 \]x^{p - 1} \equiv (x - 1)(x - 2)\cdots(x - (p - 1)) \pmod p
\[ 代入 $x \equiv p \pmod p$ 即证得定理. $\Box$. ## 003_ 莫比乌斯反演 为了进入主题 **莫比乌斯反演**，我们需要穿插一些离散组合数学的补充内容。 ### 003.1 组合基础 #### 003.1A 二项式定理 记 **二项式系数**（或者我们更熟悉的组合数）为 $\dbinom{n}{r}$ ，代表一个 $n$ 元素集中大小为 $r$ 的子集个数。 依据一些组合数学的常识，我们能够得到： [**定理3.1.1**] 二项式系数的性质 1. $$\dbinom{n}{r} = \dfrac{n!}{r!(n - r)!}\]- \[\dbinom{n}{r} = \dbinom{n}{n - r} \]
- （帕斯卡公式）对于 \(\forall k \in [1,n -1]\)
- \[\dbinom{n}{0} + \dbinom{n}{1} + \dbinom{n}{2} + \cdots + \dbinom{n}{n} = 2^n \]
解释： 对于 1，2，不作过多解释；对于 3，可以带入公式 2 ；对于 4，实质就是所有 n 元素集合的子集个数，左侧是将不同大小的子集加起来，右边可以看作子集的组合意义，即每个元素都可已选择是否放入当前子集中，根据乘法原理，子集个数就是 \(2^n\)。
[定理3.1.2（二项式定理）] 设 \(n\) 为正整数，则对所有 \(x\) 和 \(y\)，有：
\[\boxed{(x + y) ^ n = \sum _{k = 0}^{n}\dbinom{n}{k}x^{n - k}y^k} \]证明: 展开 \((x + y) ^ n\)，得到 \((x+y)(x+y)\cdots(x+y)\)。事实上，每一个形如 \(ax^{n-k}y^k\) 的项等同于在展开式的 \(n\) 个因式中选择 \(k\) 个外，和剩余的 \(n - k\) 个 \(x\)。则根据二项式系数的定义，该项的系数就是 \(\dbinom{n}{k}\)。
[定理3.1.3（范德蒙卷积）] 对所有正整数 \(n, m_1, m_2\)，有：
\[\boxed{\sum_{k = 0}^n \dbinom{m_1}{k}\dbinom{m_2}{n - k} = \dbinom{m_1+m_2}{n}} \]证明： \(\dbinom{m_1 + m_2}{n}\) 相当于从大集合 \(m_1 + m_2\) 中选 \(n\) 个人的方案，而这 \(n\) 个人中，必然有 \(k\) 个属于 \(m_1\)，\(n - k\) 个属于 \(m_2\)。所以取遍了 \(k\) 的值，也便取遍了全部取 \(n\) 个人的可能的方案。也就是左边的式子等于右边的式子。
当然，关于二项式定理还有很多有意思的公式，暂且搁置。
003.1B 容斥原理
容斥原理在前面计算欧拉函数的时候介绍过，现在我们给出一个形式化的证明。
集合相关记号约定：
- \(|A| = \mathrm{card}(A)\) 为集合 \(A\) 的大小（元素个数）.
- \(A \backslash B = \{x \mid x \in A \text{ and } x \not \in B\}\).
- \(\overline{A} = \complement _S A\) 表示在一个全集 \(S\)（一般省略）下，\(A\) 集合的补集。
- \(\bigcap \limits_{i = 1}^n A_i = A_1 \cap A_2 \cap A_3 \cap \cdots \cap A_n\)。
- \(\bigcup \limits_{i = 1}^n A_i = A_1 \cup A_2 \cup A_3 \cup \cdots \cup A_n\)。
特别地，若 \(A_1 \cap A_2 \cap \cdots \cap A_n = \varnothing\) 时，称此时 \(\bigcup \limits_{i = 1}^n A_i\) 为 无交并，记 \(\bigcup \limits_{i = 1}^n A_i = \bigsqcup \limits_{i = 1}^n A_i\)。
[定理3.1.4（容斥原理）]
我们设集合 \(S\) 中的对象涉及不同的 \(m\) 个性质 \(P_1, P_2, \cdots, P_m\)，并设子集
\[A_i = \{x\mid x \in S，且\ x\ 具有性质\ P_i\ \} \quad (i = 1, 2, \cdots, m) \]我们有集合 \(S\) 中 不具有性质 \(P_1, P_2, \cdots P_m\) 的任何性质的元素的集合 可表示为等式左右的表达式：
\[\begin{aligned} \left| \bigcap\limits_{i = 1}^{m}\overline{A_i} \right | = & \left| S \right| - \sum\limits_i \left| A_i \right| + \sum\limits_{i < j} \left| A_i \cap A_j\right| - \sum\limits_{i < j < k} \left| A_i \cap A_j \cap A_k \right| \\ & + \cdots + (-1)^m\left|A_1 \cap A_2 \cap \cdots \cap A_m \right| \tag{1} \end{aligned} \]或者记为：
\[\boxed{ \left| \bigcap\limits_{i = 1}^{m}\overline{A_i} \right | = \left| S \right| + \sum\limits_{k = 1}^{m}\left[(-1)^k\sum\limits_{a_i < a_{i+1}}^k\left|\bigcap\limits_{i=1}^m A_i\right|\right]} \tag{2} \]事实上，这个表达与如下的表达是等价的：
集合 \(S\) 中 具有性质 \(P_1, P_2, \cdots P_m\) 的所有性质的元素的集合 可表示为
\[\boxed{ \left| \bigcup\limits_{i = 1}^{m}{A_i} \right | = \sum\limits_{k = 1}^{m}\left[(-1)^{k-1}\sum\limits_{a_i < a_{i+1}}^k\left|\bigcap\limits_{i=1}^m A_i\right|\right]} \tag{3} \]证明： 假设某个元素具有 \(p_1, p_2, \cdots, p_m\) 中的 \(k\) 条性质，那么不难发现他对 \(\sum\limits_i \left| A_i \right|\) 一项的贡献为 \(\dbinom{k}{1}\)，对 \(\sum\limits_{i < j} \left| A_i \cap A_j\right|\) 一项的贡献为 \(\dbinom{k}{2}\) 以此类推，同时 \(|S|\) 中每一个元素都贡献了 \(1 = \dbinom{k}{0}\)。故可以得到他对右侧整体的贡献为：
\[\dbinom{k}{0} - \dbinom{k}{1} + \dbinom{k}{2} + \cdots + (-1)^k\dbinom{k}{k} = \sum\limits_{i = 0}^k\dbinom{n}{i}(-1)^i = (1 - 1)^k = 0 \text{（二项式定理）} \]所以具有性质的元素在等式右边的贡献为零，由于不具有任何性质的元素不属于任何 \(A_i\)，所以只在 \(|S|\) 中贡献一，所以 \((1)\) 得证。
由于 补集的交集等于并集的补集，故 \(|S| - \left| \bigcap\limits_{i = 1}^{m}\overline{A_i} \right | = \left| \bigcup\limits_{i = 1}^{m}{A_i} \right |\) 。所以 \((3)\) 式即得证。\(\Box\)
错位排列问题： 错位排列是指某个集合 \(\{1, 2, \cdots, n\}\) 中的元素排列组成的一个新排列 \(\{a_1', a_2', \cdots, a_n'\}\) 使得任意 \(a_i \ne a_i'\) 的排列。我们记对于一个 \(n\) 元素集合的错位排序的数目为 \(D_n\)，我们有：
[定理3.1.4（错位排序的计算式）] 对于 \(n \geqslant 1\)：
- \[D_n = n!\left(1 - \dfrac{1}{1!} + \dfrac{1}{2!} - \dfrac{1}{3!} +\cdots +(-1)^n\dfrac{1}{n!}\right) \]
- \[D_n = (n - 1)(D_{n-1} + D_{n - 2}) \]
证明： 第一个式子基于容斥原理，第二个式子基于组合意义。
- 设集合 \(A_i\) 为第 \(i\) 个元素在自己位置上的排列集合，不难发现实质就是求：$$
D_n = \left| \bigcap\limits_{i = 1}^{n}\overline{A_i} \right | = \left| S \right| + \sum\limits_{k = 1}{n}\left[(-1)k\sum\limits_{a_i < a_{i+1}}k\left|\bigcap\limits_{i=1}n A_i\right|\right]
f : X \times X \rightarrow \R
\[ 使得当 $x \not\preccurlyeq y$ 时，$f(x, y) = 0$。我们记所有定义在 $(X, \preccurlyeq)$ 上的满足上述条件的 **函数的集合** 为 $\mathcal{F}(X)$。 接着我们定义对于两个函数 $f,g\in \mathcal{F}(X)$，他们的 **卷积** 函数 $h = f * g$（注意 $h \in \mathcal{F}(X)$） ： \]h(x, y) =
\begin{cases}
\sum\limits_{x \preccurlyeq z \preccurlyeq y} &f(x, z)g(z, y), &&\text{if } x \preccurlyeq y, \
&0 && \text{otherwise.}
\end{cases}
\boxed{
(f * g) * h = f * (g * h)
}
((f * g) * h) (x,y) = \sum \limits_{x \preccurlyeq z_1 \preccurlyeq y} f(x,z_1) \sum\limits_{z_1 \preccurlyeq z_2 \preccurlyeq y} g(z_1, z_2)h(z_2, y)
\[ 由于偏序集的反对称性和传递性，我们可以这样变形： \]\begin{aligned}
\sum \limits_{x \preccurlyeq z_1 \preccurlyeq y} f(x,z_1) \sum\limits_{z_1 \preccurlyeq z_2 \preccurlyeq y} g(z_1, z_2)h(z_2, y) &= \sum \limits_{x \preccurlyeq z_1 \preccurlyeq z_2 \preccurlyeq y} f(x,z_1)g(z_1, z_2)h(z_2, y)\
&= \sum \limits_{x \preccurlyeq z_1 \preccurlyeq z_2} f(x,z_1)g(z_1, z_2)\sum\limits_{x \preccurlyeq z_2 \preccurlyeq y}h(z_2, y) \
&= (f * (g * h)) (x, y) \qquad \Box
\end{aligned}
\delta(x, y) :=
\begin{cases}
\ 1, &&\text{if } x = y, \
\ 0 && \text{otherwise.}
\end{cases}
\boxed{
\delta * f = f * \delta = f}
\zeta(x,y) :=
\begin{cases}
\ 1, &&\text{if } x \preccurlyeq y, \
\ 0 && \text{otherwise.}
\end{cases}
g * f = \delta
\[ **证明：** 由于偏序集的自反性（$x \preccurlyeq x$），故 $f(y,y) \ne 0$ ，我们总能找到以下 $g$ 的递归构造（公式中 $x\prec y$ 表示 $x \preccurlyeq y$ 但 $x \ne y$）： \]\begin{aligned}
g(x,y) &= -\dfrac{1}{f(y,y)}\sum\limits_{x \preccurlyeq z \prec y} g(x,z)f(z,y) \quad && (x \prec y)\
&=-\dfrac{1}{f(y,y)}\left[\left(\sum\limits_{x \preccurlyeq z \preccurlyeq y} g(x,z)f(z,y) \right) - g(x,y)f(y,y)\right] \quad && (x \preccurlyeq y)\
&= g(x,y) + \sum\limits_{x \preccurlyeq z \preccurlyeq y} g(x,z)f(z,y)&& (x \preccurlyeq y) \
\Longleftrightarrow \delta(x, y) &= \sum\limits_{x \preccurlyeq z \preccurlyeq y} g(x,z)f(z,y)&& (x \preccurlyeq y)
\end{aligned}
g = g * \delta = g * (f * h) = (g * f) * h = \delta * h = h
\[ 我们能够得到 $f*f^{-1} = f^{-1}*f = \delta$。 现在我们定义莫比乌斯函数 $\mu$ 满足： \]\boxed{\mu * \zeta = \zeta * \mu = \delta}
\[ **$\mu$ 函数的性质：** 对于 $x,y \in X$，我们有： 1. $$\sum\limits_{x \preccurlyeq z \preccurlyeq y} \mu(x,z)\zeta(z,y) = \delta(x, y)$$ 或等价于 $$\sum\limits_{x \preccurlyeq z \preccurlyeq y} \mu(x,z) = \delta(x, y)\]- \[\forall x \in X, \quad \mu(x, x) = 1 \]
- （依据 定理3.3.2 的构造）$$\begin{aligned}\mu(x,y) &= -\sum\limits_{x \preccurlyeq z \prec y} \mu(x,z) \qquad (x \prec y)\ \ &= -\sum\limits_{x \prec z \preccurlyeq y} \mu(z,y) \qquad (x \prec y) \end{aligned}$$
偏序集的直积结构： 对于两个有限偏序集 \((X, \preccurlyeq_1)\)，\((Y, \preccurlyeq_2)\)。我们定义集合
\[X\times Y = \{(x, y)\mid x \in X, \ y \in Y\} \]和其上的偏序关系 \(\preccurlyeq\) 为：
\[(x, y) \preccurlyeq (x', y')\ \text{ 当且仅当 }\ x \preccurlyeq_1 x'，\ y \preccurlyeq _2 y' \]同时 \((X\times Y, \preccurlyeq)\) 也为一个偏序集。
[定理3.3.4] 设 \(\mu_1，\mu_2\) 分别为偏序集 \((X, \preccurlyeq_1)\) 和 \((Y, \preccurlyeq_2)\) 上的莫比乌斯函数，\(\mu\) 为他们的直积的莫比乌斯函数，则：
\[\mu((x, y), (x', y')) = \mu_1(x, x') \mu_2(y,y') \qquad(x, y),(x',y')\in X \times Y \]证明： 对于 \((x',y') \preccurlyeq (x, y)\) 的情况很容易验证，所以我们只需证对于 \((x, y) \prec (x', y')\) 的情况。我们归纳地假设对于所有 \((x, y)\preccurlyeq(u,v)\prec(x',y')\) 的 \((u,v)\) 都正确，那么我们能够得到：
\[\begin{aligned} \mu((x, y), (x', y')) =& - \sum \limits_{(x, y)\preccurlyeq(u,v)\prec(x',y')} \mu((u, v), (x', y')) \\ =& - \sum \limits_{(x, y)\preccurlyeq(u,v)\prec(x',y')} \mu_1(u, x')\mu_2(v, y') \\ =& - \left(\sum \limits_{x\preccurlyeq_1 u \preccurlyeq _1 x'} \mu_1(u, x')\right)\left(\sum \limits_{y \preccurlyeq v \preccurlyeq y'} \mu_2(v, y')\right) \\ &+ \mu_1(x, x') \mu_2(y,y') \\ =& -\delta_1(x, x')\delta_2(y, y') + \mu_1(x, x') \mu_2(y,y') \\ =& \mu_1(x, x') \mu_2(y,y') \qquad \Box \end{aligned} \][定理3.3.3（莫比乌斯反演公式）]
对于一个有最小元的有限偏序集（以便下面的求和是有限的），我们定义其集上的两个函数 \(F:X\rightarrow \R\) 与 \(G: X \rightarrow \R\)，定义：
\[G(x) := \sum \limits_{z \preccurlyeq x}F(z) \quad(x \in X) \]等价于
\[F(x) = \sum\limits_{y \preccurlyeq x} G(y)\cdot\mu(y,x) \quad (x \in X) \]证明： $$\begin{align}
\sum\limits_{y \preccurlyeq x} G(y)\cdot\mu(y,x) &= \sum\limits_{y \preccurlyeq x} \mu(y, x) \sum\limits_{z \preccurlyeq y} F(z) \
&= \sum\limits_{y \preccurlyeq x}\mu(y, x) \sum\limits_{z \in X} F(z) \zeta(z,y) \
&= \sum\limits_{y \preccurlyeq x} \sum\limits_{z \in X} F(z) \zeta(z,y)\mu(y, x)\
&= \sum\limits_{z \in X} F(z) \sum\limits_{y \preccurlyeq x} \zeta(z,y)\mu(y, x)\
&= \sum\limits_{z \in X} F(z) \sum\limits_{z\preccurlyeq y \preccurlyeq x} \mu(y, x)\
&= \sum\limits_{z \in X} F(z) \delta(z,x) \
&= F(x)
\end{align}
003.3B （子集反演）再证容斥原理
容斥原理实质是莫比乌斯反演在有限偏序集上的一个实例。
我们首先定义出这个偏序集：
\[(\mathcal{P}(X_n), \subseteq) \]其中 \(\mathcal{P}(X_n) = \left\{ A_i \mid A_i \subseteq \{1, 2, 3, \cdots, n\} \right\}\)，即 \(A_i\) 是大的集合 \(\{1, 2, 3, \cdots, n\}\) 的子集，而 \(\mathcal{P}(X_n)\) 则是这些子集的集合。\(\subseteq\) 表示这个集合上的关系是这些 \(A_i\) 的包含关系。
[定理3.3.5] 在偏序集 \((\mathcal{P}(X_n), \subseteq)\) 上，若 \(A \subseteq B\)，则：
\[\mu (A, B) = (-1)^{|B| - |A|} \]证明： 使用数学归纳法，首先对任意 \(\mu (A, A) = (-1)^{0} = 1\) 成立。我们归纳假设对所有 \(A \subseteq C \subsetneqq B\)，有 \(\mu (A, C) = (-1) ^ {|C| - |A|}\) 成立。记 \(p = |B| - |A|\)，那么有：
\[\begin{aligned} \mu(A, B) &= -\sum\limits_{A\preccurlyeq C \prec B} \mu(A, C) \\ &= -\sum\limits_{A\subseteq C \subsetneqq B} (-1)^{|C| - |A|} \\ &= -\sum\limits_{k = 0}^{p - 1} (-1) ^ k \dbinom{p}{k} \end{aligned} \]最后一步是由于所有 \(C\) 集合可由 \(A\) 集合中的元素加上选取 \(|B \backslash A|\) 中的任意几个元素组成。根据二项式定理：
\[\begin{aligned} \mu(A, B) &= -\sum\limits_{k = 0}^{p - 1} (-1) ^ k \dbinom{p}{k} \\ &= -\left((1 - 1)^{p} - (-1)^{p}\dbinom{p}{p}\right)\\ &= (-1)^{p} \qquad \Box \end{aligned} \]（定理3.1.4 容斥原理）对于 \(A_1, A_2, \cdots, A_n \subseteq S\):
\[\left| \bigcap\limits_{i = 1}^{n}\overline{A_i} \right | = \left| S \right| + \sum\limits_{k = 1}^{n}\left[(-1)^k\sum\limits_{a_i < a_{i+1}}^k\left|\bigcap\limits_{i=1}^n A_i\right|\right] \]我们将下标写成集合的形式，设 \(X_n = \{1, 2, \cdots, n \}\)，则右侧取并集本质是取下标集合的子集。为了便于书写，将右侧 \(|S|\) 一项加入到求和中，我们规定 \(A_{\varnothing} = S\) 而且 \(\varnothing \in \varnothing \subseteq L\)。我们得到：
\[\left| \bigcap\limits_{i = 1}^{n}\overline{A_i} \right | = \sum\limits_{L \subseteq X_n} (-1)^{|L|} \left|\bigcap \limits_{i \in L} A_i\right| \]为了迎合子集反演中 \(\mu\) 函数的指数要求，我们将式中 \(-1\) 的指数改为 \(n - |L|\)。相应地，原式变为：
\[\left| \bigcap\limits_{\substack{i \in X_n \\ i \ne \varnothing}}\overline{A_i} \right | = \sum\limits_{L \subseteq X_n} (-1)^{n - |L|} \left|\bigcap \limits_{\substack{i\not \in L \\ \text{or } i = \varnothing}} A_i\right| \tag{1}\]
证明（莫比乌斯反演法）： 我们简记 \(B_K = \left( \bigcap \limits_{\substack{i \in K \\ i \ne \varnothing}}\overline{A_i}\right) \cap \left( \bigcap \limits_{\substack{j \not\in K \\ \text{or }j = \varnothing}}A_j\right)\)。
定义：
\[F(K) = \left| B_K \right|, \quad G(K) = \sum \limits_{L \subseteq K} F(K) \]根据偏序集 \((\mathcal P (K), \subseteq)\) 上的莫比乌斯反演公式，我们得到：
\[\begin{align} |B_K| = F(K) &= \sum \limits_{L \subseteq K} \mu(L, K) G(L) = \sum \limits_{L \subseteq K} (-1)^{|K| - |L|} \sum \limits_{J \subseteq L} F(J) \nonumber\\ &= \sum \limits_{L \subseteq K} (-1)^{|K| - |L|} \sum \limits_{J \subseteq L} \left| B_J\right| \tag{2} \end{align} \]注意到容斥原理 \((1)\) 式是实质就是当 \(K = X_n\) 时莫比乌斯反演的等价形式，所以接下来我们只需证 \((1)\) 式右边等于 \((2)\) 式右边，即对于任意 \(L \subseteq K\)，：
\[\sum \limits_{J \subseteq L} \left| B_J\right| = \left|\bigcap \limits_{\substack{i\not \in L \\ \text{or } i = \varnothing}} A_i\right| \]引理 1（求和中枚举的集合是两两不交的）： 右侧方形大并符号代表无交并（依据 003.2B 的符号约定） $$\sum \limits_{J \subseteq L} \left| B_J\right| = \left| \bigsqcup\limits_{J \subseteq L} B_K \right|$$
证明：我们假设对于 \(M,N \subseteq L\) 且 \(M \ne N\)，存在 \(s \in B_M\) 且 \(s \in B_N\)。
由于 \(M \ne N\)，则一定满足存在 \(A_i\) 使得 \(i \in M\) 且 \(i \not \in N\) （由于 \(M, N\) 是对称的，所以 \(i \in N\) 且 \(i \not \in M\) 的情况可以省略）。根据 \(B\) 的定义，由于 \(s \in B_M\) 所以 \(s \in A_i\) ；由于 \(s \in B_N\) 所以 \(s \in \overline{A_i}\)。
但是这是矛盾的。故假设不成立，不存在这样的 \(s\)，所以所有 \(B_J\) 是无交的。
引理 2 （上式的无交并与原等式右侧等价）： $$\bigcap \limits_{\substack{i\not \in L \ \text{or } i = \varnothing}} A_i = \bigsqcup\limits_{J \subseteq L} B_J$$
为了简明书写，我们将所有对于 \(\varnothing\) 的讨论略去，但是要时刻注意 \(\varnothing\) 的存在。
右边展开：$$\bigcap \limits_{\substack{i\not \in L }} A_i = \bigsqcup\limits_{J \subseteq L} \left[ \left( \bigcap \limits_{\substack{i \in J}}\overline{A_i}\right) \cap \left( \bigcap \limits_{\substack{j \not\in J }}A_j\right) \right]$$
对于右边的任意一项 \(B_J\)，注意到：
\[B_J \subseteq \bigcap \limits_{\substack{j \not\in J}}A_j \subseteq \bigcap \limits_{\substack{i\not \in L }} A_i \]每一项都包含于左边，所以他们的并也包含于左边，我们得到：
\[\bigsqcup\limits_{J \subseteq L} B_J \subseteq \bigcap \limits_{\substack{i\not \in L }} A_i \tag{3} \]对于 \(\forall s \in \bigcap _{i\not \in L} A_i\)，我们设该元素 \(s\) 不属于的 \(A_j\) 的下标 \(j\) 组成的集合为 \(C\)。这里 \(j\) 不一定是 \(L\) 中的元素。或者形式化地表达：$$C = {j \mid s \not\in A_j}$$
所以对 \(\forall s\)，若 \(j \not \in C\)，则 \(s \in A_j\)。我们能够得到（这一步读者需要深入思考）：
\[ s \in \left( \bigcap \limits_{\substack{i \in C}}\overline{A_i}\right) \cap \left( \bigcap \limits_{\substack{j \not\in C }}A_j\right) = B_C \]由于显然 \(L \subseteq C\)，而且对于所有 \(s\) 都有属于左边则属于右边，故
\[\bigcap \limits_{\substack{i\not \in L }} A_i \subseteq \bigsqcup\limits_{J \subseteq L} B_J \tag{4} \]结合 \((3)，(4)\)，引理得证。
根据以上两个引理，等式得证，原定理得证. \(\Box\)
003.3C 数论中的莫比乌斯反演
我们可以将自然数集上的整除看作一个偏序集，从而从广义的莫比乌斯反演得到 经典的莫比乌斯反演。设 \(X_n = \{1, 2, 3, \cdots, n\}\)，我们首先定义出这个偏序集：
\[(X_n, \ \mid\ ) \]右侧代表整除运算，所以 \(a \preccurlyeq b\) 当且仅当 \(a, b \in X_n, \ a \mid b\)。
经典莫比乌斯函数的性质： 特殊化我们之前已推出的莫比乌斯函数性质即可。
-
\[\mu(a, b) = \mu(1, \dfrac{a}{b})
\]
由上式，为了简明书写，我们之后记 \(\mu(n) = \mu(1, n)\)。
- \[\sum\limits_{d \mid n} \mu(n) = [n = 1] \]
- \[\mu(n) = - \sum \limits_{\substack{m \mid n \\ m \ne n}} \mu(m) \]
-
对于 \((m, n) = 1\)，有 $$\mu(mn) = \mu(m)\mu(n)$$
- \[\mu(n) = \begin{cases}\ 1 &\quad n = 1 \\ \ 0 &\quad n \text{ 含有平方因子} \\ \ (-1)^k &\quad k \text{ 为 } n \text{ 的不同素因子个数} \end{cases} \]
解释： 对于1，可仿照直积的证明归纳地证明。对于 2, 3 直接代入 003.3A 中的结论即可。对于 4，这表明经典的莫比乌斯函数是一个 积性函数。对于 4, 5，我们考虑 \(n\) 的标准分解式 \(n = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}\)。根据直积的性质不难得到。
[定理3.3.6（经典的莫比乌斯反演）] 定义 \(F\) 为正整数集上的一个函数，若：
\[G(n) = \sum \limits_{d \mid n} F(d) \]则：
\[F(n) = \sum \limits_{d \mid n} \mu(\dfrac{n}{d})G(d) \]我们在偏序集 \((X_n, \mid \ )\) 上重新考察 各类积性函数 的性质。除了我们已知的 \(\mu, \varphi, \delta, \zeta\)，我们定义
\[\mathrm{id}(n) := n \][定理3.3.7] 对于任意两积性函数 \(f, g\)，满足
\[\boxed{f * g = g * f} \][定理3.3.8]
\[\boxed{\begin{aligned} \mu * \zeta = \delta \\\mathrm{id} * \mu = \varphi \\ \varphi * \zeta = \mathrm{id} \end{aligned}} \]证明： 由 定理2.1.3 我们得到：
\[\begin{aligned} \mathrm{id} (n) &= \sum \limits_{d \mid n} \varphi (d) \\ \end{aligned} \]莫比乌斯反演后，右侧可以表示为卷积的形式：
\[\begin{aligned} \varphi(n) &= \sum \limits_{d \mid n} \mathrm{id}(d)\mu(\dfrac{n}{d}) \\ &= \sum \limits_{d \mid n} \mathrm{id}(1, d)\mu(d, n) \\ &= (\mathrm{id} * \mu) (n) \end{aligned} \]两侧同时卷积 \(\zeta\)，得：
\[\varphi * \zeta = \mathrm{id} * \mu * \zeta = \mathrm{id} * \delta = \mathrm{id} \qquad \Box \]003.3D 求一类积性函数的代码实现
求 \(\mu\) 函数的代码实现： 和求欧拉函数类似。复杂度 \(O(n)\)
int p[MAXN], vis[MAXN], mu[MAXN], cntp = 0;
void getMu(int n)
{
mu[1] = 1;
for(int i = 2; i <= n; i++){
if(!vis[i]) p[++cntp] = i, mu[i] = -1;
for(int j = 1; j <= cntp && i * p[j] <= n; j++){
vis[i * p[j]] = 1;
if(i % p[j] == 0){ mu[i * p[j]] = 0; break;}
mu[i * p[j]] = -mu[i];
}
}
}
杜教筛： 用于快速求积性函数的 前缀和。
我们设对于某个数论函数 \(f\) 的前缀和为 \(S(n) = \sum \limits_{i = 1} ^n f(i)\)。
考虑再找一个数论函数的 \(g\)，有
\[\begin{aligned} \sum \limits_{i = 1} ^n (f * g)(i) &= \sum \limits_{i = 1} ^n \sum \limits_{d \mid i} g(d) f(\dfrac{i}{d}) \\ &= \sum \limits_{i = 1} ^{n} g(i)\sum \limits_{j = 1} ^{\lfloor \frac{n}{i}\rfloor} f(j) \\ &= \sum \limits_{i = 1} ^{n} g(i) S(\lfloor\dfrac{n}{i}\rfloor) \\ &= \sum \limits_{i = 2} ^{n} g(i) S(\lfloor\dfrac{n}{i}\rfloor) + g(1)S(n) \end{aligned} \]所以我们得到
\[S(n) = \dfrac{\sum \limits_{i = 1} ^n (f * g)(i) - \sum \limits_{i = 2} ^{n} g(i) S(\lfloor\dfrac{n}{i}\rfloor)}{g(1)} \]运用杜教筛的前提是：
- 能够较快地计算 \(f * g\) 的前缀和
- 能够较快的计算 \(g\) 的单点值，后一项计算 \(S(\lfloor \dfrac{n}{i} \rfloor)\) 可以 数论分块（见附录）。
- 不要求必须为积性函数的 。
例：计算 \(\varphi\) 和 \(\mu\) 的前缀和（洛谷 P4213 【模板】杜教筛）
\[S_\varphi (n) = \dfrac{\sum \limits_{i = 1} ^n (\varphi * \zeta)(i) - \sum \limits_{i = 2} ^{n} \zeta(i) S(\lfloor\dfrac{n}{i}\rfloor)}{\zeta(1)} = \dfrac{\sum \limits_{i = 1} ^n \mathrm{id}(i) - \sum \limits_{i = 2} ^{n} \zeta(i) S(\lfloor\dfrac{n}{i}\rfloor)} {\zeta(1)} \\ S_\mu (n) = \dfrac{\sum \limits_{i = 1} ^n (\mu * \zeta)(i) - \sum \limits_{i = 2} ^{n} \zeta(i) S(\lfloor\dfrac{n}{i}\rfloor)}{\zeta(1)} = \dfrac{\sum \limits_{i = 1} ^n \delta(i) - \sum \limits_{i = 2} ^{n} \zeta(i) S(\lfloor\dfrac{n}{i}\rfloor)} {\zeta(1)} \]最后我们得到：
\[S_\varphi(n) = \dfrac{n(n + 1)}{2} - \sum \limits_{i = 2} ^{n}S(\lfloor\dfrac{n}{i}\rfloor), \quad S_\mu(n) = 1 - \sum \limits_{i = 2} ^{n}S(\lfloor\dfrac{n}{i}\rfloor) \]const int MAXN = 5000010;
typedef long long ll;
std::unordered_map<int, ll> sphi, smu;
// 使用线性筛对小范围优化
ll phi[MAXN + 10], mu[MAXN + 10];
int pi[MAXN], vis[MAXN], cntp;
void Euler()
{
phi[1] = mu[1] = 1;
for(ll i = 2; i <= MAXN; i++){
if(!vis[i]){
pi[++cntp] = i;
phi[i] = i - 1, mu[i] = -1;
}
for(ll j = 1; j <= cntp && i * pi[j] <= MAXN; j++){
vis[i * pi[j]] = 1;
if(i % pi[j]) {
phi[i * pi[j]] = phi[i] * (pi[j] - 1);
mu[i * pi[j]] = -mu[i];
}
else{
phi[i * pi[j]] = phi[i] * pi[j];
mu[i * pi[j]] = 0;
break;
}
}
}
for(int i = 2; i <= MAXN; i++) {
phi[i] += phi[i - 1];
mu[i] += mu[i - 1];
}
}
ll solvPHI(int n)
{
if(n < MAXN) return phi[n];
if(sphi[n]) return sphi[n];
ll ret = 1ll * n * (n + 1ll) / 2ll;
for(ll l = 2, r; l <= n; l = r + 1){
r = n / (n / l);
ret -= (r - l + 1ll) * solvPHI(n / l);
}
sphi[n] = ret;
return sphi[n] = ret;
}
ll solvMU(ll n)
{
if(n < MAXN) return mu[n];
if(smu[n]) return smu[n];
ll ret = 1;
for(ll l = 2, r; l <= n; l = r + 1){
r = n / (n / l);
ret -= (r - l + 1ll) * solvMU(n / l);
}
smu[n] = ret;
return ret;
}
00X_ 附录：相关概念与定理
00X.1 数论分块
数论分块旨在解决形如 \(\sum^n_{i = 1}f(i)\lfloor \frac{n}{i} \rfloor\) 的快速求和问题。我们可以将所有 \(\lfloor \frac{n}{k} \rfloor\) 相同的分到一个块中，在每块中对 \(f(x)\) 的求和就能够使用前缀和预处理出来，时间复杂度就是块的个数 \(O(\sqrt n)\) （稍后证明）。
引理1（分母换为标准形式 \(i\)）：
\[\left\lfloor \dfrac{n}{kd} \right\rfloor = \left\lfloor \dfrac{\lfloor \frac{n}{k} \rfloor}{d} \right\rfloor \]引理1的证明： 注意到 \(n = \lfloor \frac{n}{k} \rfloor \cdot k + r \ (r < k < kd)\)， 我们有：
\[LHS = \left\lfloor \dfrac{\lfloor \frac{n}{k} \rfloor \cdot k + r}{kd} \right\rfloor = \left\lfloor \dfrac{\lfloor \frac{n}{k} \rfloor}{d} + \frac{r}{kd}\right \rfloor = RHS \ \ \ \ \Box \]引理2（分块的端点）： 值等于 \(\lfloor \dfrac{n}{k} \rfloor\) 的块的右边界为 \(\left\lfloor \dfrac{n}{\lfloor \frac{n}{k} \rfloor} \right\rfloor\)。
引理2的证明： 我们设值等于 \(\lfloor \dfrac{n}{k} \rfloor\) 的块的右端点为 \(r\)，则显然有 \(r \geqslant k\)，即 \(\lfloor \dfrac{n}{r} \rfloor \leqslant \lfloor \dfrac{n}{k} \rfloor\)，故 \(r\) 只需满足 \(\lfloor \dfrac{n}{r} \rfloor \geqslant \lfloor \dfrac{n}{k} \rfloor\)，这里我们有：
\[\dfrac{n}{r} \geq \lfloor \dfrac{n}{r} \rfloor \geq \lfloor \dfrac{n}{k} \rfloor\Longrightarrow \dfrac{n}{r} \geq \lfloor \dfrac{n}{k} \rfloor \Longrightarrow r \leq \dfrac{n}{\lfloor \frac{n}{k} \rfloor} \]这里由于 \(r\) 是整数，故而 \(r \leqslant \left\lfloor \dfrac{n}{\lfloor \frac{n}{k} \rfloor} \right\rfloor\) 成立。不难验证端点处成立。\(\Box\)
引理3（分块的时间复杂度）： 形如 \(\lfloor \dfrac{n}{k} \rfloor, k \in \mathbb N^*\) 的数论分块的块数为 \(O(\sqrt{n})\)。
引理3的证明： 对于 \(k \leqslant \sqrt{n}\)，块数不超过 \(\sqrt{n}\)；对于 \(k \geqslant \sqrt{n}\)，由于 \(\lfloor \dfrac{n}{k} \rfloor \leqslant \lfloor \dfrac{n}{\sqrt{n}} \rfloor = \lfloor \sqrt{n} \rfloor\)，所以块数不超过取值数也就不超过 \(\sqrt{n}\)，总的块数不超过 \(2\sqrt{n} = O(\sqrt{n}) \ \Box\)。
如果数论分块求和形如多维的（右侧中的求积可以替换成任意包含多个不同下取整的运算符）
\[\sum^n_{i = 1}\left ( f(i) \prod_{j = 1}^{m} \lfloor \frac{a_j}{i} \rfloor \right) \]那么所有下取整的值相同的才能放到一块中，即每个块的右端点为 \(\min\limits _{j = 1}^{m} \{\left\lfloor \dfrac{a_j}{\lfloor \frac{a_j}{i} \rfloor} \right\rfloor\}\)。
数论分块的代码： 时间复杂度 \(O(\sqrt{n})\)。
long long Sum(long long n)
{
long long ans = 0;
long long l = 1, r;
while(l <= n){
r = n / (n / l);
ans += (f[r] - f[l - 1]) * (n / l); // 这里 f[i] 代表函数前缀和
l = r + 1;
}
return ans;
}
00X.2 群论相关概念
群：对于一个非空集合 \(G\)，和一个运算 \(\cdot\)，如果满足：
-
任意 \(a, b \in G\)，都有 \(a \cdot b \in G\)；
-
任意 \(a, b, c \in G\)，都有 \(a \cdot (b \cdot c) = (a \cdot b) \cdot c\)，即群的结合律；
-
存在 \(e \in G\)，使得对任意 \(a \in G\)，都有 \(a \cdot e = e \cdot a = a\)，并称 \(e\) 是群 \(G\) 的单位元；
-
对于任意 \(a \in G\)，存在 \(b \in G\)，使得 \(a \cdot b = b \cdot a = e\)，并称 \(b\) 是 \(a\) 的逆元，记为\(a^{-1}\).
则称 \((G,\cdot)\) 是一个群，表示该群和运算 \(a \cdot b\) 时，通常省略运算 \(\cdot\)，记为群 \(G\) 和 \(ab\).
对于一个群 \(G\) 和 \(a \in G\)，我们一般将 \(\underbrace{aa \cdots a}\) 简记为 \(a^n\).
群的阶：对于一个群 \(G\)，如果集合 \(G\) 的大小 \(|G|\) 是有限的，则称它为有限群，反之则称他为无限群. 对于有限群 \(G\)，\(|G|\) 称为群 \(G\) 的阶。
交换群：对于一个群 \(G\)，如果对于任意 \(a, b \in G\)，都有 \(ab = ba\)，则称这个群为 \(\text{Abel}\) 群 或 交换群. 通常交换群的运算用 \(+\) 表示，也将 \(a^n\) 记为 \(na\).
标签：preccurlyeq,OI,limits,pmod,dfrac,sum,笔记,学习,equiv From： https://www.cnblogs.com/anjack511/p/18006717/MathNote-Number