数学部分知识点
数学部分知识点
涉及的知识点
-
数论
-
线性代数
-
组合数学
-
博弈论
数论
- 质数
- 约数
- 欧拉函数
- 快速幂
- 扩展欧几里得算法
- 中国剩余定理
质数
质数的定义
-
约数只有1和他自身的整数，被称为质数或素数。
- 例如，2,3,5,7,11…
-
也就是，质数与合数的概念是针对大于1的数来定义的。所有小于等于1的整数既不是质数也不是合数。
质数的判定
-
暴力做法
-
直接利用定义，枚举从 2 到 $x-1$ 的每个数看是否能整除，时间复杂度是$O(n)$的。
-
代码
-
bool is_prim(int x) { //判定质数 if (x < 2) return false; for (int i = 2; i < x; i++) if (x % i == 0) return false; return true; }
-
-
-
优化
-
性质
- 如果 $a$ 是 $n$ 的约数，那么 $\frac{n}{a}$ 也是 $n$ 的约数。
-
对于每一对 $(a,\frac{n}{a})$，可以枚举每一对当中较小的那一个。时间复杂度可以降到$O(\sqrt{n})$
-
代码
-
bool is_prim(int x) { //判定质数 if (x < 2) return false; for (int i = 2; i <= x / i; i++) if (x % i == 0) return false; return true; } -
细节
- 不要写
i<=sqrt(n)，sqrt运算较慢 - 不要写
i*i<=n，i*i容易溢出
- 不要写
-
-
练习 洛谷 P5736
-
分解质因数
-
唯一分解定理
- 每个正整数都能够唯一的表示成它的质因数的乘积。
$$
n=p_1^{\alpha_1} p_2{ }^{\alpha_2} \cdots p_s^{\alpha_s},\quad p_1<p_2<\cdots<p_s
$$
- 每个正整数都能够唯一的表示成它的质因数的乘积。
-
朴素算法
-
思路：从小到大枚举 $n$ 的所有因子
-
代码
-
void decompose(int x) { //分解质因数 for (int i = 2; i <= x; i++) while (x % i == 0) a[i]++, x /= i; } -
细节
- 这里循环枚举的是大于2的整数，而不是枚举质因数。思考一下为什么可行。
-
-
时间复杂度 $O(n)$
-
-
优化
-
性质
- $n$ 中最多只包含一个大于$\sqrt{n}$的质因数
-
代码
-
void decompose(int x) { //分解质因数 for (int i = 2; i <= x / i; i++) while (x % i == 0) a[i]++, x /= i; if (x > 1) a[x]++; }
-
-
举例
-
x=280 i=2, a[2]=3,x=35 i=3,4, i=5, a[5]=1,x=7 7>1 a[7]=1
-
-
时间复杂度
- $O(\sqrt{n})$
- 最好$O(\log n)$，最坏 $O(\sqrt{n})$ 的
- 当$n=2^k$的时候，时间复杂度就是$O(\log n)$
- 当n是质数，枚举 $\sqrt{n}$ 次。
-
练习 洛谷 P2043
-
筛素数
-
朴素做法
-
思想
- 依次删掉2的倍数，3的倍数，4的倍数，5的倍数……筛完之后剩下的就是质数
-
代码
-
void get_prim(int n) { //朴素做法 for (LL i = 2; i <= n; i++) { if (!vis[i]) { prim[++cnt] = i; } for (LL j = i + i; j <= n; j += i) vis[j] = true; } }
-
-
时间复杂度
- 对于每个$i$，筛的次数是 $\frac{n}{i}$
- 从2开始筛，筛的次数是$\frac{n}{2}+\frac{n}{3}+\cdots+\frac{n}{n}=n(\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n})$
- 当$n\rightarrow+\infty$时，$1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}=\ln n+c$，其中$c$是欧拉常数
- 又因为 $n\ln n < n \log_{2} n$的，所以时间复杂度可以认为是 $O(n \log n)$
-
-
埃氏筛法
-
思想
- 不用把每个数的倍数删掉，只需要把质数的倍数删掉就可以了
-
代码
-
void get_prim(int n) { //埃氏筛法 for (LL i = 2; i <= n; i++) { if (!vis[i]) { prim[++cnt] = i; for (LL j = i * i; j <= n; j += i) vis[j] = 1; } } } -
细节
- 这里
j枚举的时候是从i*i开始枚举的，因为i*2~i*(i-1)中的所有合数已经被筛掉了
- 这里
-
-
举例
-
n=20 i=2: 质数{2}; 筛掉{4,6,8,10,12,14,16,18,20} i=3: 质数{3}; 筛掉{9,12,15,18} i=4: i=5: 质数{5} i=6: i=7: 质数{7} i=8,9,10 i=11: 质数{11} i=12: i=13: 质数{13} i=14,15,16 i=17: 质数{17} i=18: i=19: 质数{19} i=20:
-
-
时间复杂度 $O(n \log (\log n))$
- 当$n=2^{32}$时， $\log (\log n)=5$
-
-
线性筛法（欧拉筛法）
-
思想
- 每一个合数，只会被他的最小质因子筛掉
-
流程
- 从小到大枚举每个数
i- 如果当前数没划掉，必定是质数，记录该质数
- 枚举已记录的质数
prim[j]，与i乘构成合数i * prim[j]- 筛：
- 合数未越界，则划掉合数；
- 停：
- 如果合数已越界则中断
- 若ⅰ是质数，则最多枚举到自身中断
- 若ⅰ是合数，则最多枚举到自身的最小质因数中断
- 筛：
- 从小到大枚举每个数
-
代码
-
void get_prim(int n) { //线性筛法 for (int i = 2; i <= n; i++) { if (!vis[i]) prim[++cnt] = i; for (int j = 1; prim[j] <= n / i; j++) { vis[i * prim[j]] = 1; if (i % prim[j] == 0) break; //条件成立时，说明prim[j]是i的最小质因子 } } }
-
-
举例
-
n=30 i=2: 质数{2}; 筛掉{4}; (2%2==0) break; i=3: 质数{3}; 筛掉{6,9}; (3%3==0) break; i=4: 筛掉{8}; (4%2==0) break; i=5: 质数{5}; 筛掉{10,15,25}; (5%5==0) break; i=6: 筛掉{12}; (6%2==0) break; i=7: 质数{7}; 筛掉{14,21};(35>30); i=8: 筛掉{16}; (8%2==0) break; i=9: 筛掉{18,27}; (9%3==0) break; i=10: 筛掉{20}; (10%2==0) break; i=11: 质数{11}; 筛掉{22};(33>30); i=12: 筛掉{24};(12%2==0) break; …… i=16: (32>30)
-
-
算法的正确性
- 筛掉的每一个数，一定是通过它的最小质因子筛掉的。
- 筛数的过程
vis[i * prim[j]] = 1;，分两种情况讨论- 当
i % prim[j] ==0时，prim[j]一定是i的最小质因子，也一定是i*prim[j]的最小质因子。 - 当
i % prim[j] !=0时，那么prim[j]一定小于i的所有质因子，所以prim[j]是i*prim[j]的最小质因子。
- 当
- 综上，
i*prim[j]一定是被自己的最小质因子筛掉的。
- 筛数的过程
- 任何一个合数，一定会被筛掉
- 任何一个合数，都会存在一个最小质因子，假设是
pj。那么当i枚举到x/pj的时候，那么我们就会在这个时候通过vis[i * prim[j]] = 1;把它筛掉。
- 任何一个合数，都会存在一个最小质因子，假设是
- 筛掉的每一个数，一定是通过它的最小质因子筛掉的。
-
时间复杂度
- $O(n)$
- 每个质数只被记录一次，每个合数只被筛掉一次
- 线性筛法在10^7的时候，会比埃氏筛法快一倍
-
练习 洛谷 P3383
-
约数
试除法求约数
-
核心思想
- 从小到大判断，类似质数判定。
- 如果$d|n$，那么$\frac{n}{d}|n$
-
代码
-
vector<int> get_divisors(int x) { vector<int> res; for (int i = 1; i <= x / i; i ++ ) if (x % i == 0) { res.push_back(i); if (i != x / i) res.push_back(x / i); } sort(res.begin(), res.end()); return res; } -
细节
- 如果
i == x / i，说明两个约数相同，只要记录一次。
- 如果
-
-
时间复杂度 $O(\sqrt{n})$
- 一个数的约数个数的期望是$O(\log {n})$的，这里排序的时间复杂度是$O(\log {n}\log {\log {n}})$，小于 $O(\sqrt{n})$
- 1是$n$个数的约数，2是$\frac{n}{2}$个数的约数，3是$\frac{n}{3}$个数的约数，……加起来求平均不超过 $O(\log {n})$
- 一个数的约数个数的期望是$O(\log {n})$的，这里排序的时间复杂度是$O(\log {n}\log {\log {n}})$，小于 $O(\sqrt{n})$
约数个数
-
定理
- 若 $n=\prod_{i=1}^s p_i{ }^{\alpha_i}$, 则 $d(n)=\prod_{i=1}^s\left(\alpha_i+1\right)$
- 证明
- $p_i{ }^{\alpha_i}$ 的约数有 $p_i^0, p_i^1, \cdots, p_i^{\alpha_i}$ 共 $\left(\alpha_i+1\right)$ 个, 根据乘法原理, $d(n)=\prod_{i=1}^s\left(\alpha_i+1\right)$ 。
-
题目
-
给定 $n$ 个正整数 $a_i$ ，请你输出这些数的乘积的约数个数，答案对 $10^9+7$ 取模。
-
代码
-
#include <iostream> #include <algorithm> #include <unordered_map> #include <vector> using namespace std; typedef long long LL; const int N = 110, mod = 1e9 + 7; int main() { int n; cin >> n; unordered_map<int, int> primes; while (n -- ) { int x; cin >> x; for (int i = 2; i <= x / i; i ++ ) while (x % i == 0) { x /= i; primes[i] ++ ; } if (x > 1) primes[x] ++ ; } LL res = 1; for (auto p : primes) res = res * (p.second + 1) % mod; cout << res << endl; return 0; }
-
-
-
题目
-
给一个数 $n\left(n \leq 1 \times 10^6\right)$, 输出 $1 \sim n$ 每个数的约数个数。
-
思路
- 两个数组
a[i]：整数 i 的最小质因子的次数d[i]：整数 i 的约数的个数
- 若 $i$ 是质数
a[i]=1，d[i]=2。
- 在线性筛中, 每个合数 $m$ 都是被最小的质因子筛掉的。
- 设 $p_j$ 是 $m$ 的最小质因子, 则 $m$ 通过 $m=p_j \times i$ 筛掉。
- 寻找
a[m]和a[i]、d[m]和d[i]之间的关系- 若
i%p[j]==0, 则 $p_j$ 一定是 $i$ 的最小质因子。a[m]=a[i]+1d[i]=(a[i]+1)*…，d[m]=(a[m]+1)*…，所以d[m]=d[i]/a[m]*(a[m]+1)
- 若
i%p[j]!=0，则 $i$ 不包含质因子 $p_j$ 。a[m] = 1d[m]=d[i]*(1+1)
- 若
- 两个数组
-
代码
-
void get_d(int n) { //筛法求约数个数 d[1] = 1; for (int i = 2; i <= n; i++) { if (!vis[i]) { p[++cnt] = i; a[i] = 1; d[i] = 2; } for (int j = 1; i * p[j] <= n; j++) { int m = i * p[j]; vis[m] = 1; if (i % p[j] == 0) { a[m] = a[i] + 1; d[m] = d[i] / a[m] * (a[m] + 1); break; } else { a[m] = 1; d[m] = d[i] * 2; } } } } -
时间复杂度 $O(n)$
-
-
举例
-
约数之和
-
定理
-
若 $n=\prod_{i=1}^s p_i^{\alpha_i}$, 则 $f(n)=\prod_{i=1}^s \sum_{j=0}^{\alpha_i} p_i^j$
-
证明
- $p_i{ }^{\alpha_i}$ 的约数有 $p_i^0, p_i^1, \cdots, p_i^{\alpha_i}$ 共 $\left(\alpha_i+1\right)$ 个，其约数和为 $\sum_{j=0}^{\alpha_i} p_i^j$,
- 根据乘法原理, $f(n)=\prod_{i=1}^S \sum_{j=0}^{\alpha_i} p_i^j$
-
举例
-
$$
\begin{aligned}
& 12=2^2 \times 3^1 \
& f(12)={1+2+4} \times{1+3}=7 \times 4=28
\end{aligned}
$$
-
-
题目
-
给定 $n$ 个正整数 $a_i$ ，请你输出这些数的乘积的约数之和，答案对 $10^9+7$ 取模。
-
代码
-
#include <iostream> #include <algorithm> #include <unordered_map> #include <vector> using namespace std; typedef long long LL; const int N = 110, mod = 1e9 + 7; int main() { int n; cin >> n; unordered_map<int, int> primes; while (n -- ) { int x; cin >> x; for (int i = 2; i <= x / i; i ++ ) while (x % i == 0) { x /= i; primes[i] ++ ; } if (x > 1) primes[x] ++ ; } LL res = 1; for (auto p : primes) { LL a = p.first, b = p.second; LL t = 1; while (b -- ) t = (t * a + 1) % mod; res = res * t % mod; } cout << res << endl; return 0; }
-
-
-
题目
-
给一个数 $n\left(n \leq 1 \times 10^6\right)$, 输出 $1 \sim n$ 每个数的约数和。
-
思路
g[i]：整数 i 的最小质因子的约数和，$g[i]=p_j0+p_j1+\cdots+p_j^{\alpha_j}$f[i]：整数 i 的约数和- 若 $i$ 是质数
g[i]=f[i]=i+1
- 在线性筛中, 每个合数 $m$ 都是被最小的质因子筛掉的。
- 设 $p_j$ 是 $m$ 的最小质因子, 则 $m$ 通过 $m=p_j \times i$ 筛掉。
- 寻找
g[m]和g[i]、f[m]和f[i]之间的关系- 若
i%p[j]==0, 则 $p_j$ 一定是 $i$ 的最小质因子。- $g[i]=p_j0+p_j1+\cdots+p_j{\alpha_j}$，$g[m]=p_j0+p_j1+\cdots+p_j$，所以有
g[m]=g[i]*p[j]+1 - $f[i]=g[i] \times \cdots$，$f[m]=g[m] \times \cdots$，所以有
f[m]=f[i]/g[i]*g[m]
- $g[i]=p_j0+p_j1+\cdots+p_j{\alpha_j}$，$g[m]=p_j0+p_j1+\cdots+p_j$，所以有
- 若
i%p[j]!=0，则 $i$ 不包含质因子 $p_j$- $g[m]=1+p_j$
- $f[m]=g[m] \times f[i]$
- 若
-
代码
-
#include <iostream> using namespace std; const int N = 1000010; int p[N], vis[N], cnt; //g[i]表示i的最小质因子的1+p^1+...+p^k int g[N], f[N];//f[i]表示i的约数和 void get_f(int n){ //筛法求约数和 g[1] = f[1] = 1; for(int i=2; i<=n; i++){ if(!vis[i]){ p[++cnt] = i; g[i] = f[i] = i+1; } for(int j=1; i*p[j]<=n; j++){ int m = i*p[j]; vis[m] = 1; if(i%p[j] == 0){ g[m] = g[i]*p[j]+1; f[m] = f[i]/g[i]*g[m]; break; } else{ g[m] = p[j]+1; f[m] = f[i]*g[m]; } } } } int main(){ int n; cin >> n; get_f(n); for(int i=1; i<=n; i++) printf("%d\n",f[i]); return 0; }
-
-
举例
-
逆元
欧拉函数
-
定义
- $1 \sim n$ 中与 $n$ 互质的数的个数称为欧拉函数, 记为 $\varphi(n)$
-
举例
- $\varphi(1)=1, \varphi(2)=1, \varphi(3)=2, \varphi(4)=2, \varphi(5)=4$
-
欧拉函数的性质
- 若 $p$ 是质数, 则 $\varphi(p)=p-1$
- 因为任何一个质数都是和它前面的整数互质
- 若 $p$ 是质数, 则 $\varphi\left(p^k\right)=(p-1) p^{k-1}$
- $1……p……2p……3p……p^k$
- 其中，$p,2p,3p,\cdots，pk$都和$pk$不互质共$p^{k-1}$个
- 所以和$p^k$互质的一共有$(p-1) p^{k-1}$
- 积性函数：若 $g c d(m, n)=1$, 则 $\varphi(m n)=\varphi(m) \varphi(n)$
- 若 $p$ 是质数, 则 $\varphi(p)=p-1$
-
欧拉函数的计算公式
-
$$
\varphi(n) = n \times \frac{p_1-1}{p_1} \times \frac{p_2-1}{p_2} \times \cdots \times \frac{p_s-1}{p_s}
$$ -
证法1
-
由唯一分解定理 $n=\prod_{i=1}^S p_i{ }^{\alpha_i}=p_1{ }^{\alpha_1} p_2{ }^{\alpha_2} \cdots p_s{ }^{\alpha_s}$,
-
$
\begin{aligned}
\varphi(n) & =\prod_{i=1}^s \varphi\left(p_i^{\alpha_i}\right) \
& =\prod_{i=1}^s p_i^{\alpha_i-1}\left(p_i-1\right) \
& =\prod_{i=1}^s p_i^{\alpha_i}\left(1-\frac{1}{p_i}\right) \
& =\prod_{i=1}^s p_i^{\alpha_i} \times \prod_{i=1}^s\left(1-\frac{1}{p_i}\right) \
& =n \times \prod_{i=1}^s \frac{p_i-1}{p_i} \
& =n \times \frac{p_1-1}{p_1} \times \frac{p_2-1}{p_2} \times \cdots \times \frac{p_s-1}{p_s}
\end{aligned}
$ -
第一个等号用到了性质3，第二个等号用到了性质2，第三个等号是把括号里面的$p_{i}$提出来，第四个等号是改变连乘的顺序，第五个等号是唯一分解定理和通分。
-
-
-
证法2
-
从1~n中去掉$p_1,p_2,\cdots,p_k$所有的倍数，加上$p_ip_j$的倍数，减去$p_ip_j*p_k$的倍数，……
-
所以个数就是
$
n-\frac{n}{p_1}-\frac{n}{p_2}-\cdots-\frac{n}{p_3} \
+\frac{n}{p_1p_2}+\frac{n}{p_1p_3}+\cdots \
-\frac{n}{p_1p_2p_3} - \cdots
$ -
把欧拉公式的计算式展开，可以看到和这个式子是相等的
-
-
所以，欧拉函数仅由 $n$ 和质因子决定，与次数无关。
-
举例
- $\varphi(12)=12 \times \frac{2-1}{2} \times \frac{3-1}{3}=4$
-
-
试除法求欧拉函数
-
代码
-
#include <iostream> using namespace std; const int N = 1e9 + 10; int phi(int n) { //试除法求欧拉函数 int res = n; for (int i = 2; i * i <= n; i++) { if (n % i == 0) { res = res / i * (i - 1); while (n % i == 0) n /= i; } } if (n > 1) res = res / n * (n - 1); return res; } int main() { int n; cin >> n; cout << phi(n) << endl; return 0; }
-
-
时间复杂度 $O(\sqrt{n})$
-
举例
-
-
筛法求欧拉函数
-
求出1~n当中每个数的欧拉函数
-
思路
- 若 $i$ 是质数
- $\operatorname{phi}[i]=i-1$
- 在线性筛中, 每个合数 $m$ 都是被最小的质因子筛掉的。
- 设 $p_j$ 是 $m$ 的最小质因子, 则 $m$ 通过 $m=p_j \times i$ 筛掉。
- 若
i%p[j]==0, 则 $i$ 包含了 $m$ 的所有质因子- $\varphi(m)=m \times \prod_{k=1}^S \frac{p_k-1}{p_k}=p_j \times i \times \prod_{k=1}^S \frac{p_k-1}{p_k}=p_j \times \varphi(i)$
- 举例
- $\varphi(12)=\varphi(2 \times 6)=2 \times \varphi(6)$
- 若
i%p[j]!=0, 则$i$和$p_j$互质- $\varphi(m)=\varphi\left(p_j \times i\right)=\varphi\left(p_j\right) \times \varphi(i)=\left(p_j-1\right) \times \varphi(i)$
- 举例
- $\varphi(75)=\varphi(3 \times 25)=(3-1) \times \varphi(25)$
- 若 $i$ 是质数
-
代码
-
#include <iostream> using namespace std; const int N = 1000010; int p[N], vis[N], cnt; int phi[N]; void get_phi(int n) { //筛法求欧拉函数 phi[1] = 1; for (int i = 2; i <= n; i++) { if (!vis[i]) { p[cnt++] = i; phi[i] = i - 1; } for (int j = 0; i * p[j] <= n; j++) { int m = i * p[j]; vis[m] = 1; if (i % p[j] == 0) { phi[m] = p[j] * phi[i]; break; } else phi[m] = (p[j] - 1) * phi[i]; } } } int main() { int n; cin >> n; get_phi(n); for (int i = 1; i <= n; i++) printf("%d\n", phi[i]); return 0; }
-
-
举例
-
快速幂
-
给你三个整数 $a, b, p$, 求 $a^b \bmod p$
-
思路
- $a^n=a \times a \times \cdots \times a$, 暴力的计算需要 $\mathrm{O}(\mathrm{n})$ 的时间。
- 快速幂使用二进制拆分和倍增思想, 仅需要 $O(\log n)$ 的时间。
- 对 $n$ 做二进制拆分
- 例如， $3{13}=3=3^8 \cdot 3^4 \cdot 3^1$
- 对 $a$ 做平方倍增，例如， $3^1, 3^2, 3^4, 3^8 \cdots \cdots$ 。
- $\mathrm{n}$ 有 $\log \mathrm{n}+1$ 个二进制位, 我知道了 $a^1, a^2, a^4, a^8, \ldots, a{2{\operatorname{logn}}}$ 后, 只需要计算 $\log n+1$ 次乘法就可以了。
- 对 $n$ 做二进制拆分
-
快速幂可以应用在任何具有结合律的运算中， 例如，取模运算、矩阵乘法等。
例如，
$$
\left(3^{13}\right) % p=\left(\left(3^8\right) % p \cdot\left(3^4\right) % p \cdot\left(3^1\right) % p\right) % p
$$ -
举例
-
代码
-
#include <iostream> using namespace std; typedef long long LL; int a, b, p; int quickpow(LL a, int n, int p) { int res = 1; while (n) { if (n & 1) res = res * a % p; a = a * a % p; n >>= 1; } return res; } int main() { cin >> a >> b >> p; int s = quickpow(a, b, p); printf("%d^%d mod %d=%d\n", a, b, p, s); return 0; }
-
-
练习 洛谷 P1226
乘法逆元
- 定义
- 若 $a, b$ 互质，且满足同余方程 $a x \equiv 1(\bmod b)$, 则称 $\boldsymbol{x}$ 为 $\boldsymbol{a}$ 模 $\boldsymbol{b}$ 的乘法逆元，记作 $\boldsymbol{a}^{-1}$
- 举例
- $8 x \equiv 1(\bmod 5)$, 解得 $x=2,7,12 \ldots$
费马小定理
-
定理
- 若 $p$ 为质数，且 $a, p$ 互质，则 $a^{p-1} \equiv 1(\mod p)$
-
举例
- $4^{3-1} \equiv 1(\bmod 3)$
-
证明
- 构造一个与 $p$ 互质的序列 $A={1,2,3, \cdots, p-1}$,
- 则 $a \times A_i(\bmod p)$ 的余数必是独一无二的
- 原因
- 假设 $a A_i(\bmod p)$ 与 $a A_j(\bmod p)$ 的余数都是 $r$ ，
- 则 $a A_i=x p+r, a A_j=y p+r$,
- 即 $a\left(A_i-A_j\right)=(x-y) p$ ，
- 左边不是 $p$ 的倍数，而右边是 $p$ 的倍数，矛盾
- 原因
- 因为 $a \times A_i(\bmod p)p$，所以 $a \times A_i(\bmod p)$ 必与 $A_i(\bmod p)$ 的余数集合相同
- 所以 $a^{p-1} \times \prod_{i=1}^{p-1} A_i \equiv \prod_{i=1}^{p-1} A_i(\bmod p)$
-
举例：
- $p=5, A={1,2,3,4}, a=2$ 。
- 则 $a A={2,4,6,8}, a A % p={2,4,1,3}, A % p={1,2,3,4}$
-
求乘法逆元
-
给两个数 $a, p, p$ 是质数, 求 $a$ 模 $p$ 的乘法逆元
-
由费马小定理
$a^{p-1} \equiv 1(\bmod p)$, 得 $a \times a^{p-2} \equiv 1(\bmod p)$, -
所以 $a^{p-2}$ 就是 $a$ 模 $p$ 的乘法逆元。用快速幂求即可。
-
代码
#include<iostream> using namespace std; typedef long long LL; int a, p; int quickpow(LL a, int b, int p) { int res = 1; while (b) { if (b & 1) res = res * a % p; a = a * a % p; b >>= 1; } return res; } int main() { cin >> a >> p; if (a % p) printf("%d\n", quickpow(a, p - 2, p)); return 0; } ``` - 时间复杂度 $O(\log p)$ -
欧拉定理
-
剩余类（同余类）
- 给定一个正整数 $n$ ，把所有整数根据模 $n$ 的余数 $r \in [0, n-1]$ 分为 $n$ 类, 每一类表示为 $C_r=n x+r$ 的形
式，这类数所构成的一个集合称为模 $n$ 的剩余类。 - 例 $n=5, r=3$, 则 $C_3=5 x+3$ 为模 5 的一个剩余类。
- 给定一个正整数 $n$ ，把所有整数根据模 $n$ 的余数 $r \in [0, n-1]$ 分为 $n$ 类, 每一类表示为 $C_r=n x+r$ 的形
-
完全剩余系 (完系)
- 给定一个正整数 $n$, 有 $n$ 个不同的模 $n$ 的剩余类，从这 $n$ 个不同的剩余类中各取出一个元素，总共 $n$ 个数，将这些数构成一个新的集合，则称这个集合为模 $n$ 的完全剩余系。
- 例 $n=5$, 则 ${0,1,2,3,4}$ 是一个模 5 的完全剩余系， ${5,1,-3,8,9}$ 也是一个模 5 的完全剩余系。
-
简化剩余系 (缩系)
- 给定一个正整数 $n$, 有 $\varphi(n)$ 个不同的模 $n$ 的余数 $r$ 与 $n$ 互质的剩余类, 从这 $\varphi(n)$ 个剩余类中各取出一个元素, 总共 $\varphi(n)$ 个数，将这些数构成一个新的集合，则称这个集合为模 $n$ 的简化剩余系。
- 例 $n=5$, 则 ${1,2,3,4}$ 是一个模 5 的简化剩余系, $n=10$, 则 ${1,3,7,9}$ 是一个模 10 的简化剩余系, 显然模 $n$ 的简化剩余系中所有的数都与 $n$ 互质。
-
欧拉定理
-
若 $\operatorname{gcd}(a, m)=1$, 则 $a^{\varphi(m)} \equiv 1(\bmod m)$
- 当 $m$ 为质数时, 由于 $\varphi(m)=m-1$, 代入欧拉定理 可得到费马小定理 $a^{m-1} \equiv 1(\bmod m)$ 。
-
举例
- $
\begin{aligned}
& a=3, m=4 \text {, 则 } 3^{\varphi(4)} \equiv 3^2 \equiv 1(\bmod 4) \
& a=3, m=5 \text {, 则 } 3^{\varphi(5)} \equiv 3^4 \equiv 1(\bmod 5)
\end{aligned}
$
- $
-
-
证明
- 构造一个与 $m$ 互质的序列。
- 设 $\left{r_1, r_2, \cdots, r_{\varphi(m)}\right}$ 是一个模 $m$ 的简化剩余系，则 $\left{a r_1, a r_2, \cdots, a r_{\varphi(m)}\right}$ 也是一个模 $m$ 的简化剩余系。
- 所以 $\prod_{i=1}^{\varphi(m)} r_i \equiv \prod_{i=1}^{\varphi(m)} a r_i \equiv a^{\varphi(m)} \prod_{i=1}^{\varphi(m)} r_i(\bmod m)$，可约去 $\prod_{i=1}^{\varphi(m)} r_i$, 即得 $a^{\varphi(m)} \equiv 1(\bmod m)$ 。
- 构造一个与 $m$ 互质的序列。
-
补充：
- 费马小定理和欧拉定理
扩展欧拉定理
-
扩展欧拉定理没有要求 $\operatorname{gcd}(a, m)=1$
-
$
a^b \equiv\left{\begin{array}{lll}
a^b, & b<\varphi(m), & (\bmod m) \
a^{b \bmod \varphi(m)+\varphi(m)}, & b \geq \varphi(m), & (\bmod m)
\end{array}\right.
$ -
举例
- 如果用欧拉定理，则结果不对: $a=2, m=4, b=1, \quad 2^1 \neq 2^{1 \bmod 2+2}(\bmod 4)$
- 如果用扩展欧拉定理，则结果正确: $a=2, m=4, b=6,2^6 \equiv 2^{6 \bmod 2+2}(\bmod 4)$
-
题目 洛谷 P5091
-
给你三个正整数 $a, m, b$, 你需要求： $a^b \bmod m$
-
数据范围
$$
1 \leq \mathrm{a} \leq 10^9, \quad 1 \leq \mathrm{m} \leq 10^8, \quad 1 \leq \mathrm{b} \leq 10^{20000000}
$$
-
-
代码
-
#include <iostream> using namespace std; typedef long long LL; int a, b, m, phi, flag; char s[20000005]; int get_phi(int n) { //求欧拉函数 int res = n; for (int i = 2; i * i <= n; i++) { if (n % i == 0) { res = res / i * (i - 1); while (n % i == 0) n /= i; } } if (n > 1) res = res / n * (n - 1); return res; } int depow(int phi) { //降幂 int b = 0; for (int i = 0; s[i]; i++) { b = b * 10 + (s[i] - '0'); if (b >= phi) flag = 1, b %= phi; } if (flag) b += phi; return b; } int qpow(LL a, int b) { //快速幂 int res = 1; while (b) { if (b & 1) res = res * a % m; a = a * a % m; b >>= 1; } return res; } int main() { scanf("%d%d%s", &a, &m, s); phi = get_phi(m); b = depow(phi); printf("%d", qpow(a, b)); return 0; }
-
公约数
求最大公约数
-
性质
- 如果 $d|a$，$d|b$，那么$d|a+b$，$d|ax+by$
-
欧几里得算法（辗转相除法）
- $gcd(a,b)=gcd(b,a \mod b)$
- 证明
- 设 $a>b, a % b=a-k b$ ，其中 $k=\left\lfloor\frac{a}{b}\right\rfloor$
- (1) 若 $d$ 是 $(a, b)$ 的公约数,
- 则 $d \mid a$ 且 $d \mid b$ ， 则 $d \mid(a-k b)$,
- 则 $d \mid(a % b)$ 故 $d$ 也是 $(b, a % b)$ 的公约数。
- (2) 若 $d$ 是 $(b, a % b)$ 的公约数,
- 则 $d \mid b$ 且 $d \mid(a-k b)$,
- 则 $d|(a-k b+k b)=d| a$, 故 $d$ 也是 $(a, b)$ 的公约数。
- 所以 $(a, b)$ 和 $(b, a % b)$ 的公约数是相同的，故最大公约数也相同。
- $gcd(a,0)=a$
-
代码
-
LL gcd(LL a, LL b) { return b == 0 ? a : gcd(b, a % b); }
-
-
举例
-
gcd(28,16) gcd(16,12) gcd(12,4) gcd(4,0) return 4
-
-
欧几里得算法求 $\operatorname{gcd}(a, b)$ 如果代入负数, 结果会返回负数
- 例: $\operatorname{gcd}(8,-4)=-4$
-
时间复杂度是 $O(\log n)$
- 当我们求 $\operatorname{gcd}(a, b)$ 的时候，会遇到两种情况:
- $a<b$ ，这时候 $\operatorname{gcd}(a, b)=\operatorname{gcd}(b, a)$ ；
- $a \geq b$ ，这时候 $\operatorname{gcd}(a, b)=\operatorname{gcd}(b, a \bmod b)$ ，而对 $a$ 取模会让 $a$ 至少折半。这意味着这一过程最多发生 $O(\log n)$ 次。
- 第一种情况发生后一定会发生第二种情况，因此第一种情况的发生次数一定不多于第二种情况的发生次数。 从而我们最多递归 $O(\log n)$ 次就可以得出结果。
- 当我们求 $\operatorname{gcd}(a, b)$ 的时候，会遇到两种情况:
-
练习 洛谷 P1029
-
本题应满足三个约束条件:
- $\operatorname{gcd}(p, q)=x$
- $\operatorname{lcm}(p, q)=y$
- $p q=\operatorname{gcd}(p, q) \operatorname{lcm}(p, q)=x y$
-
证明:
- 设 $p=a d, q=b d$, 则 $l c m(p, q)=a b d$
- 因为 $p, q$ 乘积是定值, 所以枚举 $p$ 即可。
- 因为 $p, q$ 是成对的, 所以枚举到 $\sqrt{x y}$ 即可。
- 三个条件不是独立的，满足两条即可。
-
代码
-
#include <iostream> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; LL x, y, ans; LL gcd(LL a, LL b) { return b == 0 ? a : gcd(b, a % b); } int main() { cin >> x >> y; LL t = x * y; for (LL i = 1; i * i <= t; i++) if (t % i == 0 && gcd(i, t / i) == x) ans += 2; if (x == y) ans--; cout << ans; return 0; }>
-
-
裴蜀定理
-
裴蜀定理
- 一定存在整数 $x, y$, 满足 $a x+b y=g c d(a, b)$
- 举例
- 例 $4 x+6 y=2$, 有整数解 $x=-1, y=1$ 。
- 而 $4 x+6 y=3$, 即 $x=\frac{3-6 y}{4}$ 无整数解。
-
证明
-
设取整数 $x_0, y_0$ 时， $a x+b y$ 的最小正整数为 $s$ 即 $a x_0+b y_0=s$
-
证明 $\operatorname{gcd}(a, b) \mid s$
- 因 $\operatorname{gcd}(a, b)\left|a x_0, \operatorname{gcd}(a, b)\right| b y_0$，故 $\operatorname{gcd}(a, b) \mid s$
-
证明 $s \mid \operatorname{gcd}(a, b)$
-
设 $a=q s+r(0 \leq r<s)$
-
则
$$
\begin{aligned}
r & =a-q s \
& =a-q\left(a x_0+b y_0\right) \
& =a\left(1-q x_0\right)+b\left(-q y_0\right) \
& =a x+b y
\end{aligned}
$$ -
因 $\mathrm{s}$ 是最小正整数, 故 $r=0$
-
所以 $s \mid a$，同理 $s \mid b$,
-
故 $s \mid \operatorname{gcd}(a, b)$
-
-
得 $s=\operatorname{gcd}(a, b)$
-
-
推广1
- 一定存在整数 $x, y$, 满足 $a x+b y=\operatorname{gcd}(a, b) \times n$
- 例 $4 x+6 y=8$, 有整数解 $x=-4, y=4$ 。
- 一定存在整数 $x, y$, 满足 $a x+b y=\operatorname{gcd}(a, b) \times n$
-
推广2
- 一定存在整数 $X_1 \cdots X_i$, 满足 $\sum_{i=1}^n A_i X_i=\operatorname{gcd}\left(A_1, A_2, \cdots, A_n\right)$
- 例 $4 x_1+6 x_2+2 x_3=4$, 有整数解 $x_1=1, x_2=0, x_3=0$ 。
- 一定存在整数 $X_1 \cdots X_i$, 满足 $\sum_{i=1}^n A_i X_i=\operatorname{gcd}\left(A_1, A_2, \cdots, A_n\right)$
-
注意
- 如果系数 $A_i$ 为负数, 求 $g c d$ 时结果可能为负。可代入其绝对值, 确保所求最大公约数为正数, 这样并不会影响解的存在。
-
题目 洛谷 P4549
-
给定一个包含 $\mathrm{n}$ 个元素的整数序列 $A$ ，记作 $A_1, A_2, \ldots, A_n$ 。 求另一个包含 $\mathrm{n}$ 个元素的待定整数序列 $X$,
记 $S=\sum_{i=1}^n A_i \times X_i$, 使得 $S>0$ 且 $S$ 尽可能的小。 -
代码
-
#include<iostream> #include<cmath> using namespace std; int n, a, s; int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a; s = gcd(s, abs(a)); } cout << s; return 0; }
-
-
扩展欧几里得算法
-
解决裴蜀定理中 $x,y$ 的取值问题
- 求 $a x+b y=g c d(a, b)$ 的一组整数解
-
扩展欧几里得算法
- 当 $b=0$ 时
- $a x+b y=a$ 故而 $x=1, y=0$
- 当 $b \neq 0$ 时
- 由欧几里得算法, $\operatorname{gcd}(a, b)=\operatorname{gcd}(b, a % b)$
- 由裴蜀定理，
$$
\begin{aligned}
\operatorname{gcd}(a, b) & =a x+b y \
\operatorname{gcd}(b, a % b) & =b x_1+(a % b) y_1 \
& =b x_1+\left(a-\left[\frac{a}{b}\right] \times b\right) y_1 \
& =a y_1+b\left(x_1-\frac{a}{b} y_1\right)
\end{aligned}
$$- 所以 $x=y_1, y=x_1-\frac{a}{b} y_1$
- 可以用递归算法，先求出下一层的 $x_1, y_1$,
再回代到上一层, 层层回代, 可求特解 $\left(x_0, y_0\right)$ - 构造通解
$$
\left{\begin{array}{l}
x=x_0+\frac{b}{\operatorname{gcd}(a, b)} * k \
y=y_0-\frac{a}{\operatorname{gcd}(a, b)} * k
\end{array} \right.
$$-
-
举例
- $8 x+6 y=2$, 解: $(1,-1),(4,-5),(7,-9) \cdots$
-
代码
-
int exgcd(int a, int b, int &x, int &y) { if (b == 0) { x = 1, y = 0; return a; } int x1, y1, d; d = exgcd(b, a % b, x1, y1); x = y1, y = x1 - a / b * y1; return d; }
-
- 当 $b=0$ 时
-
举例
-
补充
- 扩展欧几里得算法(喻邻溥)
-
应用：求不定方程 $\boldsymbol{a x}+\boldsymbol{b} y=\boldsymbol{c}$ 的一组整数解
-
若 $\operatorname{gcd}(a, b) \mid c$，则有整数解
- 先用扩欧算法求 $a x+b y=\operatorname{gcd}(a, b)$ 的解 再乘以 $c / \operatorname{gcd}(a, b)$ ， 即得原方程的特解 $\left(x_0, y_0\right)$
- 例: $8 x+6 y=6$, 解得 $x=3, y=-3$
- 构造通解
- $\left{\begin{array}{l}x=x_0+\frac{b}{\operatorname{gcd}(a, b)} * k \ y=y_0-\frac{a}{\operatorname{gcd}(a, b)} * k\end{array} \quad\right.$
- 考虑 $a x+b y=0$ 构造
- 先用扩欧算法求 $a x+b y=\operatorname{gcd}(a, b)$ 的解 再乘以 $c / \operatorname{gcd}(a, b)$ ， 即得原方程的特解 $\left(x_0, y_0\right)$
-
若 $\operatorname{gcd}(a, b) \nmid c$ ，则无整数解。
- 例: $8 x+6 y=3, x=\frac{3-6 y}{8}$
-
代码
-
#include <iostream> #include <cstring> #include <algorithm> using namespace std; int exgcd(int a, int b, int &x, int &y) { if (b == 0) { x = 1, y = 0; return a; } int x1, y1, d; d = exgcd(b, a % b, x1, y1); x = y1, y = x1 - a / b * y1; return d; } int main() { int a, b, c, x, y; cin >> a >> b >> c; int d = exgcd(a, b, x, y); if (c % d == 0) printf("%d %d", c / d * x, c / d * y); else puts("none"); return 0; }
-
-
-
应用：扩展欧几里得算法求同余方程
-
问题
- 如果 $x$ 存在整数解, 则输出任意一个; 如果不存在, 则输出 none
- 例: $8 x \equiv 4(\bmod 6)$, 整数解 $x=2$
-
思路
- 把同余方程转化为不定方程
- 由 $a x \equiv b(\bmod m)$
- 得 $a x=m(-y)+b$
- 即 $a x+m y=b$
- 由裴蜀定理，当 $\operatorname{gcd}(a, m) \mid b$ 时 有解
- 用扩欧算法 求 $a x+m y=\operatorname{gcd}(a, m)$ 的解 把 $x$ 乘以 $b / \operatorname{gcd}(a, m)$ 即得原方程的特解
- 把同余方程转化为不定方程
-
代码
-
#include <iostream> #include <cstring> #include <algorithm> using namespace std; int exgcd(int a, int b, int &x, int &y) { if (b == 0) { x = 1, y = 0; return a; } int x1, y1, d; d = exgcd(b, a % b, x1, y1); x = y1, y = x1 - a / b * y1; return d; } int main() { int a, b, m, x, y; scanf("%d%d%d", &a, &b, &m); int d = exgcd(a, m, x, y); if (b % d == 0) printf("%d", 1ll * x * b / d % m); else puts("none"); return 0; }
-
-
-
应用：扩展欧几里得算法求乘法逆元
-
问题
- $a$ 与 $m$ 互质时, 对于方程 $a x \equiv \mathbf{1}(\bmod m)$, 求 $a$ 的乘法逆元 $x \quad(0<\mathrm{x}<\mathrm{m})$
- 例: $3 x \equiv 1(\bmod 4)$, 整数解 $x=3$
-
思路
- 乘法逆元转化为不定方程 等价变形 $a x+m y=1$
- 扩欧算法 求 $a x+m y=\operatorname{gcd}(a, m)$ 的解 $x$
- $(x % m+m) % m$ 即答案
- 这一操作可以保证得到最小正整数
- 例: $x=-7, m=5$, 则 $(-7 % 5+5) % 5=3$
- 例: $x=7, m=5$ ，则 $(7 % 5+5) % 5=2$
- 这一操作可以保证得到最小正整数
-
代码
-
#include <iostream> #include <cstring> #include <algorithm> using namespace std; int exgcd(int a,int b,int &x,int &y){ if(b == 0){ x = 1, y = 0; return a; } int x1, y1, d; d = exgcd(b, a%b, x1, y1); x = y1, y = x1-a/b*y1; return d; } int main(){ int a, m, x, y; scanf("%d%d", &a, &m); exgcd(a, m, x, y); printf("%d", (x%m+m)%m); return 0; }
-
-
时间复杂度 $O(\log\max(a,b))$
-
中国剩余定理
-
问题
- $
\left{\begin{array}{c}
x \equiv r_1\left(\bmod m_1\right) \
x \equiv r_2\left(\bmod m_2\right) \
\vdots \
x \equiv r_n\left(\bmod m_n\right)
\end{array}\right.
$
其中模数 $m_1, m_2, \cdots, m_n$ 为两两互质的整数， 求 $x$ 的最小非负整数解。
- $
-
来源：
- 《孙子算经》
- 有物不知其数，三三数之剩二，五五数之剩三， 七七数之剩二。问物几何?
- 《孙子算经》
-
中国剩余定理 (Chinese Remainder Theorem, CRT)
- 计算所有模数的积 $M$
- 计算第 $i$ 个方程的 $c_i=\frac{M}{m_i}$
- 计算 $c_i$ 在模 $m_i$ 意义下的逆元 $c_i^{-1}$
- $x=\sum_{i=1}^n r_i c_i c_i^{-1}(\bmod M)$
-
-
证明
-
先证明 $x=\sum_{i=1}^n r_i c_i c_i^{-1}$ 满足每个 $x \equiv r_i\left(\bmod m_i\right)$ 。
-
当 $i \neq j$ 时, $c_j \equiv 0\left(\bmod m_i\right)$, 则 $c_j c_j^{-1} \equiv 0\left(\bmod m_i\right)$
-
当 $i=j$ 时, $c_i \not \equiv 0\left(\bmod m_i\right)$, 则 $c_i c_i^{-1} \equiv 1\left(\bmod m_i\right)$
-
故
- $
\begin{aligned}
& x \equiv \sum_{j=1}^n r_j c_j c_j^{-1}\left(\bmod m_i\right) \
& \equiv r_i c_i c_i^{-1} \quad\left(\bmod m_i\right) \
& \equiv r_i \quad\left(\bmod m_i\right) \
&
\end{aligned}
$
- $
-
-
再看对 $x=\sum_{i=1}^n r_i c_i c_i^{-1}$ 模 $M$ 后，是不是对每个式子成立
- $\sum_{i=1}^n r_i c_i c_i^{-1}(\bmod M)$ 对 $m_i$ 来说，只是减去了 $m_i$ 的若干倍, 不影响余数 $r_i$ 。证毕
-
-
题目 洛谷 P1495
-
代码
-
#include <iostream> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; LL n, a[11], b[11]; LL exgcd(LL a, LL b, LL &x, LL &y) { if (b == 0) { x = 1, y = 0; return a; } LL d, x1, y1; d = exgcd(b, a % b, x1, y1); x = y1, y = x1 - a / b * y1; return d; } LL CRT(LL m[], LL r[]) { LL M = 1, ans = 0; for (int i = 1; i <= n; i++) M *= m[i]; for (int i = 1; i <= n; i++) { LL c = M / m[i], x, y; exgcd(c, m[i], x, y); ans = (ans + r[i] * c * x % M) % M; } return (ans % M + M) % M; } int main() { scanf("%lld", &n); for (int i = 1; i <= n; ++i) scanf("%lld%lld", a + i, b + i); printf("%lld\n", CRT(a, b)); return 0; }
-
-
时间复杂度
- $O(n \log c)$
-
扩展中国剩余定理
-
问题
- 求解线性同余方程组
$
\left{\begin{array}{c}
x \equiv r_1\left(\bmod m_1\right) \
x \equiv r_2\left(\bmod m_2\right) \
\cdots \
x \equiv r_n\left(\bmod m_n\right)
\end{array}\right.
$
其中 $m_1, m_2, \cdots, m_n$ 为不一定两两互质的整数，求 $x$ 的最小非负整数解。
- 求解线性同余方程组
-
中国剩余定理 (CRT) 已不可行
- 其构造解 $x=\sum_{i=1}^n r_i c_i c_i^{-1}(\bmod M)$
- 其中 $c_i x \equiv 1\left(\bmod m_i\right)$ ， 即 $c_i x+m_i y=1=\operatorname{gcd}\left(c_i, m_i\right)$
- 根据裴蜀定理， $c_i, m_i$ 应该互质, $c_i=\frac{m_1 \times \cdots \times m_n}{m_i}$
- 如果 $c_i, m_i$ 不互质, 则 $c_i^{-1}$ 不存在, 算法失效
-
扩展中国剩余定理
- 前两个方程可以转化为不定方程
- $x \equiv r_1\left(\bmod m_1\right), x \equiv r_2\left(\bmod m_2\right)$
- 转化为不定方程
- $x=m_1 p+r_1=m_2 q+r_2$
- 移项，得不定方程
- $m_1 p-m_2 q=r_2-r_1$
- 由裴蜀定理，可知
- 当 $\operatorname{gcd}\left(m_1, m_2\right) \nmid\left(r_2-r_1\right)$ 时，无解
- 当 $\operatorname{gcd}\left(m_1, m_2\right) \mid\left(r_2-r_1\right)$ 时，有解
- 在有解的情况下，由扩欧算法先求出前两个方程的解
- 特解 $p=p * \frac{r_2-r_1}{g c d}, q=q * \frac{r_2-r_1}{g c d}$
- 通解 $P=p+\frac{m_2}{g c d} * k, Q=q-\frac{m_1}{g c d} * k$
- 由 $P,Q$ 可以构造 $x$
- $x=m_1 P+r_1=\frac{m_1 m_2}{g c d} * k+m_1 p+r_1$
- 那么，前两个方程等价合并为一个方程 $x \equiv r(\bmod m)$
- 其中 $r=m_1 p+r_1, \quad m=\frac{m_1 m_2}{gcd}=\operatorname{lcm}\left(m_1, m_2\right)$
- 所以 $n$ 个同余方程只要合并 $n-1$ 次，即可求解
- 前两个方程可以转化为不定方程
-
代码
-
#include <iostream> #include <cstring> #include <algorithm> using namespace std; typedef __int128 LL; const int N = 100005; LL n, m[N], r[N]; LL exgcd(LL a, LL b, LL &x, LL &y) { if (b == 0) { x = 1, y = 0; return a; } LL d, x1, y1; d = exgcd(b, a % b, x1, y1); x = y1, y = x1 - a / b * y1; return d; } LL EXCRT(LL m[], LL r[]) { LL m1, m2, r1, r2, p, q; m1 = m[1], r1 = r[1]; for (int i = 2; i <= n; i++) { m2 = m[i], r2 = r[i]; LL d = exgcd(m1, m2, p, q); if ((r2 - r1) % d) { return -1; } p = p * (r2 - r1) / d; //特解 p = (p % (m2 / d) + m2 / d) % (m2 / d); r1 = m1 * p + r1; m1 = m1 * m2 / d; } return (r1 % m1 + m1) % m1; } int main() { scanf("%lld", &n); for (int i = 1; i <= n; ++i) scanf("%lld%lld", m + i, r + i); printf("%lld\n", EXCRT(m, r)); return 0; }
-
线性代数
线性方程组
-
一般形式
- $
\begin{aligned}
& \mathrm{a}{11} \mathrm{x}1+\mathrm{a} \mathrm{x}2+\mathrm{a} \mathrm{x}3+\cdots+\mathrm{a}{1 \mathrm{n}} \mathrm{x}{\mathrm{n}}=\mathrm{b}1 \
& \mathrm{a} \mathrm{x}1+\mathrm{a} \mathrm{x}2+\mathrm{a} \mathrm{x}3+\cdots+\mathrm{a}{2 \mathrm{n}} \mathrm{x}{\mathrm{n}}=\mathrm{b}2 \
& \cdots \cdots \
& \mathrm{a} 1} \mathrm{x}1+\mathrm{a} 2} \mathrm{x}2+\mathrm{a} 3} \mathrm{x}3+\cdots+\mathrm{a}{\mathrm{nn}} \mathrm{x}{\mathrm{n}}=\mathrm{b}_{\mathrm{n}}
\end{aligned}
$
- $
-
矩阵形式
-
$
\left[\begin{array}{ccccc}
a_{11} & a_{12} & a_{13} & \ldots & a_{1 n} \
a_{21} & a_{22} & a_{23} & \ldots & a_{2 n} \
\vdots & \vdots & \vdots & & \vdots \
a_{n 1} & a_{n 2} & a_{n 3} & \ldots & a_{n n}
\end{array}\right] \times\left[\begin{array}{c}
x_1 \
x_2 \
\vdots \
x_n
\end{array}\right]=\left[\begin{array}{c}
b_1 \
b_2 \
\vdots \
b_n
\end{array}\right]
$ -
即 $A X=B$。
- $A$ 是 $n \times n$ 矩阵, $X$ 是 $n \times 1$ 矩阵， $B$ 是 $n \times 1$ 矩阵
-
-
增广矩阵
- $
\left[\begin{array}{lccccr}
a_{11} & a_{12} & a_{13} & \ldots & a_{1 n} & b_1 \
a_{21} & a_{22} & a_{23} & \ldots & a_{2 n} & b_2 \
\vdots & \vdots & \vdots & & \vdots & \vdots \
a_{n 1} & a_{n 2} & a_{n 3} & \ldots & a_{n n} & b_n
\end{array}\right]
$
- $
-
矩阵的初等行变换
- 交换两行
- 把某一行乘一个非 0 的数
- 把某行的若干倍加到另一行上去
高斯消元法
-
思想
- 先把系数矩阵消成上三角矩阵, 再从下到上回代求解
- 先把系数矩阵消成上三角矩阵, 再从下到上回代求解
-
流程
- 枚举主元, 找到主元下面系数不是0的一行
- 有时候为了保证精度，会选择主元绝对值最大的行
- 把这一行与主元行交换
- 把主元系数变成1
- 把主元下面的系数变成 0
- 枚举主元, 找到主元下面系数不是0的一行
-
举例
-
解的三种情况
-
唯一解
-
$i$ 可以枚举完 $n$ 行
-
$
\left[\begin{array}{llll}
1 & 1 & 1 & 6 \
0 & 1 & 2 & 8 \
0 & 0 & 1 & 3
\end{array}\right]
$
-
-
无解
-
$a[i][i]=0, b \neq 0$
-
$
\left[\begin{array}{llll}
1 & 1 & 1 & 6 \
0 & 1 & 2 & 3 \
0 & 0 & 0 & 3
\end{array}\right] \begin{aligned}
& x_2+2 x_3=3 \
& x_2+2 x_3=6
\end{aligned}
$
-
-
无穷多解
-
$a[i][i]=0, b=0$
-
$
\left.\left[\begin{array}{llll}
1 & 1 & 1 & 6 \
0 & 1 & 2 & 3 \
0 & 0 & 0 & 0
\end{array}\right] \begin{array}{r}
x_2+2 x_3=3 \
2 x_2+4 x_3=6
\end{array}\right]
$
-
-
-
代码
-
#include <iostream> #include <algorithm> #include <cmath> using namespace std; const int N = 110; const double eps = 1e-6; int n; double a[N][N]; //增广矩阵 int gauss() { for (int i = 1; i <= n; ++i) { //第i主元 for (int k = i; k <= n; ++k) //换非0行 if (fabs(a[k][i]) > eps) { swap(a[k], a[i]); break; } if (fabs(a[i][i]) < eps) return 0; for (int j = n + 1; j >= i; j--) //变1 a[i][j] /= a[i][i]; for (int k = i + 1; k <= n; k++) //变0 for (int j = n + 1; j >= i; j--) a[k][j] -= a[k][i] * a[i][j]; } for (int i = n - 1; i >= 1; i--) //回代 for (int j = i + 1; j <= n; j++) a[i][n + 1] -= a[i][j] * a[j][n + 1]; return 1; //存在唯一解 } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) for (int j = 1; j <= n + 1; j++) scanf("%lf", &a[i][j]); if (gauss()) for (int i = 1; i < n + 1; i++) printf("%.2lf\n", a[i][n + 1]); else puts("No Solution"); return 0; }
-
-
// 高斯消元法补充 #include<bits/stdc++.h> #define maxn 1005 #define INF 2147483647 #define eps (1e-15) using namespace std; int n, ans; double a[maxn][maxn]; int gauss(){ int r=0, c=0; for(c=0, r=0;c<n;c++){ int t=r; for(int i=r;i<n;i++){ if(fabs(a[i][c])>fabs(a[t][c])){ t=i; } } if(fabs(a[t][c])<eps){ continue; } for(int i=c;i<=n;i++) swap(a[t][i], a[r][i]); for(int i=n;i>=c;i--) a[r][i]/=a[r][c]; for(int i=r+1;i<n;i++){ if(fabs(a[i][c])>eps){ for(int j=n;j>=c;j--){ a[i][j]-=a[r][j]*a[i][c]; } } } r++; } if(r<n){ for(int i=r;i<n;i++){ if(fabs(a[i][n])>eps){ return -1; } } return 0; } for(int i=n-1;i>=0;i--){ for(int j=i+1;j<n;j++){ a[i][n]-=a[i][j]*a[j][n]; } } return 2147483647; } int main() { cin>>n; for(int i=0;i<n;i++){ for(int j=0;j<=n;j++){ cin>>a[i][j]; } } ans=gauss(); if(ans==2147483647){ for(int i=0;i<n;i++){ if(a[i][n]==0) printf("x%d=0\n", i+1); else printf("x%d=%.2lf\n", i+1, a[i][n]); } return 0; } cout<<ans; return 0; } -
练习 洛谷 P3389
高斯约旦消元法
-
思路
- 先把系数矩阵消成主对角矩阵, 再除以主元
- 先把系数矩阵消成主对角矩阵, 再除以主元
-
流程
- 每轮循环, 主元所在行不变, 主元所在列消成 0
-
举例
-
代码
-
#include <iostream> #include <algorithm> #include <cmath> using namespace std; const int N = 110; const double eps = 1e-6; int n; double a[N][N]; //增广矩阵 bool Gauss_Jordan() { for (int i = 1; i <= n; ++i) { //第i主元 for (int k = i; k <= n; ++k) //换非0行 if (fabs(a[k][i]) > eps) { swap(a[k], a[i]); break; } if (fabs(a[i][i]) < eps) return 0; for (int k = 1; k <= n; ++k) { //对角化 if (k == i) continue; for (int j = n + 1; j >= i; --j) a[k][j] -= a[k][i] / a[i][i] * a[i][j]; } } for (int i = 1; i <= n; ++i) a[i][n + 1] /= a[i][i]; //除以主元 return 1; //存在唯一解 } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) for (int j = 1; j <= n + 1; j++) scanf("%lf", &a[i][j]); if (Gauss_Jordan()) for (int i = 1; i <= n; i++) printf("%.2lf\n", a[i][n + 1]); else puts("No Solution"); }
-
矩阵求逆
-
逆矩阵
-
对于方阵 $A$, 若存在方阵 $B$, 使得 $A \times B=B \times A=I$, 则称 $B$ 为 $A$ 的逆矩阵, 记为 $A^{-1}$ 。
-
单位矩阵 $I$
- $$
\left[\begin{array}{ccccc}
1 & \cdots & 0 & \cdots & 0 \
0 & \cdots & 1 & \cdots & 0 \
0 & \cdots & 0 & \cdots & 1
\end{array}\right]
$$
- $$
-
-
-
给出 $n$ 阶方阵 $A$, 求解其逆矩阵 $A^{-1}$ 的方法
-
- 构造 $n \times 2 n$ 的矩阵 $(A, I)$
- 用高斯-约旦消元法将其化简为 $\left(I, A^{-1}\right)$, 即可得到 $A$ 的逆矩阵 $A^{-1}$ 。
- 证明:
- $A X=I$ 可以看做 $n$ 组 $n$ 元线性方程组的矩阵形式
- 增广矩阵的初等行变换不改变解的值
- 对 $A X=I$ 两边同乘以 $A^{-1}$，得 $A^{-1}(A X)=A^{-1} I$，即$I X=A^{-1}$ 和 $A X=I$ 的解是一致的。
- 只要对增广矩阵 $(A,I)$ 进行初等行变换成，使得左边的 $A$ 变成 $I$，右边的增广部分就是 $A^{-1}$ 。
- 如果左部出现了全 0 行, 则矩阵 $A$ 不可逆。
-
-
代码
-
#include<iostream> #include<cstdio> #include<cmath> #define LL long long using namespace std; const int N = 405, P = 1e9 + 7; int n; LL a[N][N << 1]; LL quickpow(LL a, LL b) { LL ans = 1; while (b) { if (b & 1) ans = ans * a % P; a = a * a % P; b >>= 1; } return ans; } bool Gauss_Jordan() { for (int i = 1; i <= n; ++i) { //枚举主元的行列 int r = i; for (int k = i; k <= n; ++k) //找非0行 if (a[k][i]) { r = k; break; } if (r != i) swap(a[r], a[i]); //换行 if (!a[i][i]) return 0; int x = quickpow(a[i][i], P - 2); //求逆元 for (int k = 1; k <= n; ++k) { //对角化 if (k == i) continue; int t = a[k][i] * x % P; for (int j = i; j <= 2 * n; ++j) a[k][j] = ((a[k][j] - t * a[i][j]) % P + P) % P; } for (int j = 1; j <= 2 * n; ++j) //除以主元 a[i][j] = (a[i][j] * x % P); } return 1; } int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) scanf("%lld", &a[i][j]), a[i][i + n] = 1; if (Gauss_Jordan()) for (int i = 1; i <= n; ++i) { for (int j = n + 1; j <= 2 * n; ++j) printf("%lld ", a[i][j]); puts(""); } else puts("No Solution"); return 0; }
-
- 练习 洛谷 P4783
组合数学
组合数的计算
-
递推
-
问题
- 有 $q(q \leq 10000)$ 组询问, 每组询问两个整数 $n, m(1 \leq m \leq n \leq 2000)$, 求 $C_n^m \bmod \left(10^9+7\right)$ 的值。
-
思路
- $C_nm=C_{n-1}m+C_{n-1}^{m-1}$
- $C_n^m$ 构成了杨辉三角
-
代码
-
#include <iostream> using namespace std; const int N = 2010, P = 1e9 + 7; int C[N][N]; void init() { for (int i = 0; i < N; i++) C[i][0] = 1; for (int i = 1; i < N; i++) for (int j = 1; j <= i; j++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % P; } int main() { init(); int T, n, m; cin >> T; while (T--) { cin >> n >> m; printf("%d\n", C[n][m]); } return 0; }
-
-
时间复杂度 $O(n^2)$
-
-
快速幂
-
问题
- 有 $q(q \leq 10000)$ 组询问, 每组询问两个整数 $n, m\left(1 \leq m \leq n \leq 10^5\right)$, 求 $C_n^m \bmod \left(10^9+7\right)$ 的值。
-
思路
- 用 $C_n^m=\frac{n !}{(n-m) ! m !}$ 直接计算。
- 开两个数组分别存模意义下的阶乘和阶乘的逆元
- 用 $f[x]$ 存 $x !(\bmod p)$ 的值,
- 用 $g[x]$ 存 $(x !)^{-1}(\bmod p)$ 的值。
- 因为 $p$ 是质数且 $n, m$ 都小于 $p$, 即 $n, m$ 与 $p$ 互质，所以 根据费马小定理 $a \cdot a^{p-2} \equiv 1(\bmod p)$，可以用 快速幂 求逆元。
- 查询 $C_n^m(\bmod p)=f[n] * g[n-m] * g[m](\bmod p)$
-
代码
-
#include <iostream> using namespace std; typedef long long LL; const int N = 100010, P = 1e9 + 7; LL f[N], g[N]; LL qpow(LL a, int b) { LL res = 1; while (b) { if (b & 1) res = res * a % P; a = a * a % P; b >>= 1; } return res; } void init() { f[0] = g[0] = 1; for (int i = 1; i < N; i++) { f[i] = f[i - 1] * i % P; g[i] = g[i - 1] * qpow(i, P - 2) % P; } } LL getC(LL n, LL m) { return f[n] * g[m] % P * g[n - m] % P; } int main() { init(); int q, n, m; cin >> q; while (q--) { cin >> n >> m; printf("%lld\n", getC(n, m)); } return 0; }
-
-
时间复杂度 $O(n\log P)$
-
-
卢卡斯定理
-
问题
- 给定整数 $n, m, p$ 的值, 求出 $C_n^m(\bmod p)$ 的值。 其中 $1 \leq m \leq n \leq 10^{18}, 1 \leq p \leq 10^5$ ，保证 $p$ 为质数。
-
卢卡斯定理
-
$C_n^m \equiv C_{n / p}^{m / p} C_{n \bmod p}^{m \bmod p}(\bmod p)$ ，其中 $p$ 为质数。
- $n \bmod p$ 和 $m \bmod p$ 一定是小于 $p$ 的数, 可以直接求解
- $C_{n / p}^{m / p}$ 可以继续用 Lucas 定理求解。
-
边界条件
- 当 $m=0$ 时, 返回 1 。
-
证明
-
引理1
- ${C}_p^x \equiv {0} (\mod {p}), \quad 0<x<p$
- 证明
- 因 $C_p^x=\frac{p !}{x !(p-x) !}=\frac{p(p-1) !}{x(x-1) !(p-x) !}=\frac{p}{x} C_{p-1}^{x-1}$，故 $C_p^x \equiv p \cdot \operatorname{inv}(x) C_{p-1}^{x-1} \equiv 0(\bmod p)$ 。
- 证明
- ${C}_p^x \equiv {0} (\mod {p}), \quad 0<x<p$
-
引理2
- $(1+x)^p \equiv 1+x^p(\bmod p)$
- 证明
- 由二项式定理 $(1+x)p=\sum_{i=0}p C_p^i x^i$，由引理1知, 只剩 $i=0, p$ 两项, 得证。
- 证明
- $(1+x)^p \equiv 1+x^p(\bmod p)$
-
令 $n=a p+b, m=c p+d$
-
一方面
- $ (1+x)^n \equiv \sum_{i=0}^n C_n^i x^i \quad (\mod p) $
-
另一方面
- $
\begin{aligned}
& (1+x)^n \equiv(1+x)^{a p+b} \
& \equiv\left((1+x)p\right)a \cdot(1+x)^b \
& \equiv\left(1+xp\right)a \cdot(1+x)^b \
& \equiv \sum_{i=0}^a C_a^i x^{i p} \cdot \sum_{j=0}^b C_b^j x^j \quad (\mod p) \
&
\end{aligned}
$
- $
-
由对应次幂的系数相等，可得
- $C_n^m \equiv C_a^c C_b^d(\bmod p)$
-
即 $C_n^m \equiv C_{n / p}^{m / p} C_{n \bmod p}^{m \bmod p}(\bmod p)$ 。
-
-
-
代码
-
#include <iostream> using namespace std; typedef long long LL; const int N = 100010; LL f[N], g[N]; LL qpow(LL a, int b, int p) { LL res = 1; while (b) { if (b & 1) res = res * a % p; a = a * a % p; b >>= 1; } return res; } void init(int p) { f[0] = g[0] = 1; for (int i = 1; i <= p; i++) { f[i] = f[i - 1] * i % p; g[i] = g[i - 1] * qpow(i, p - 2, p) % p; } } LL getC(int n, int m, int p) { return f[n] * g[m] * g[n - m] % p; } int lucas(LL n, LL m, int p) { if (m == 0) return 1; return lucas(n / p, m / p, p) * getC(n % p, m % p, p) % p; } int main() { int q, n, m, p; cin >> q; while (q--) { cin >> n >> m >> p; init(p); printf("%d\n", lucas(n + m, n, p)); } return 0; }
-
-
时间复杂度 $O\left(p \log p+\log _p n\right)$
-
练习 洛谷 P3807
-
隔板法
-
应用
- 求线性不定方程的整数解的组数
- 求相同元素分组的方案数
-
正整数和的组数
- 问题：
- 若 $x_i \geq 1$, 求 $x_1+x_2+\cdots+x_k=n$ 的整数解的组数。
- 现有 $n$ 个 完全相同 的元素, 将其分为 $k$ 组，保证每 组至少有一个元素, 一共有多少种分法?
- 答案
- 把 $n$ 个相同的球排成一行, 有 $n-1$ 个空。 拿 $k-1$ 块板子插入到 $n-1$ 个空里, 把球分成 $k$ 组 即在 $n-1$ 个空里选择 $k-1$ 个空插板子, 所以答案 就是 $C_{n-1}^{k-1}$。
- 问题：
-
非负整数和的组数
- 问题：
- 若 $x_i \geq 0$, 求 $x_1+x_2+\cdots+x_k=n$ 的整数解的组数。
- 答案
- 令 $y_i=x_i+1$, 则 $y_i \geq 1$，则 $y_1+y_2+\cdots+y_k=n+k=m$，转化为情况1, 所以答案是 $C_{m-1}{k-1}=C_{n+k-1}$
- 问题：
-
不同下界整数和的组数
- 问题：
- 求 $x_1+x_2+\cdots+x_k=n$ 的整数解的组数, 其中 $x_i \geq a_i \geq 0, \quad \sum a_i \leq n_0$
- 答案
- 令 $y_i=x_i-a_i+1$, 则 $y_i \geq 1$，则 $y_1+y_2+\cdots+y_k=n-\sum a_i+k=m$，转化为情况1, 所以答案为 $C_{m-1}{k-1}=C_{n-\sum} a_i+k-1$
- 问题：
-
练习 洛谷 P1771
容斥原理
-
集合的并
- $$
\left|\bigcup_{i=1}^n S_i\right|=\sum_{m=1}n(-1) \sum_{a_i<a i+1}\left|\bigcap_{i=1}^m S_{a_i}\right|
$$
- $$
-
集合的交
- $$
\left|\bigcap_{i=1}^n S_i\right|=|U|-\left|\bigcup_{i=1}^n \overline{S_i}\right|
$$
- $$
卡特兰数
-
从格点 $(0,0)$ 走到格点 $(n, n)$, 只能向右或向上走, 并且不能越过 对角线的路径的条数，就是卡特兰数，记为 $H_n$ 。
-
求解
- 先求路径总数, 在 $2 n$ 次移动中选 $n$ 次向右移动, 即 $C_{2 n}^n$ 。
- 再求非法路径, 即越过对角线的路径。
- 把 $y=x+1$ 这条线画出来, 碰到即说明是一条非法路径。所有的非法路径与这条线有至少一个交点, 把第一个交点设为 $(a, a+1)$。
- 把 $(a, a+1)$ 之后的路径全部按照 $y=x+1$ 这条线对称过去, 这样, 最后 的终点就会变成 $(n-1, n+1)$ 。
- 所有非法路径对称后都唯一对应着一条到 $(n-1, n+1)$ 的路径,
- 所以非法路径数就是 $C_{2 n}^{n-1}$
- 合法路径数就是 $C_{2 n}^n-C_{2 n}^{n-1}$ 。
-
卡特兰数的相关问题
- 两种操作A,B，要求任意时刻B的次数不能超过A的次数
- 有 $2 n$ 个人排成一行进入剧场。入场费 5 元。其中只有 $n$ 个人有一张 5 元钞票，另外 $n$ 人只有 10 元钞票，剧院无其它钞票，问有多少种方法使得只要有 10 元的人买票，售票处就有 5 元的 钞票找零?
- 一个有 $n$ 个 0 和 $n$ 个 1 组成的字串, 且所有的前缀字串皆满足 1 的个 数不超过 0 的个数。这样的字串个数有多少?
- 包含 $n$ 组括号的合法运算式的个数有多少?
- 一个栈的进栈序列为 $1,2,3, \cdots, n$, 有多少个不同的出栈序列?
- 图形划分
- 在圆上选择 $2 n$ 个点, 将这些点成对连接起来使得所得到的 $n$ 条弦不相 交的方法数?
- 通过连结顶点而将 $n+2$ 边的凸多边形用$n-1$条对角线分隔成互不重叠的三角形，有多少种方案?
- 两种操作A,B，要求任意时刻B的次数不能超过A的次数
-
卡特兰数的通项公式
-
-
$H_n=C_{2 n}^n-C_{2 n}^{n-1}$
-
$H_n=\frac{1}{n+1} C_{2 n}^n$
-
$H_n=\frac{4 n-2}{n+1} H_{n-1}$
-
$H_n= \begin{cases}\sum_{i=1}^n H_{i-1} H_{n-i} & n \geq 2, n \in \mathbf{N}_{+} \ 1 & n=0,1\end{cases}$
>
-
-
代码
-
#include <iostream> using namespace std; int n; long long f[20]; int main() { cin >> n; f[0] = 1; for (int i = 1; i <= n; i++) f[i] = f[i - 1] * (4 * i - 2) / (i + 1); cout << f[n] << endl; return 0; }
-
-
练习 洛谷 P1044
博弈论
概念
- 公平组合游戏
- 公平组合游戏(Impartial Combinatorial Game, ICG) 是满足以下特征的一类问题:
- (1) 有两个玩家,游戏规则对两人是公平的;
- (2) 游戏的状态有限, 能走的步数也有限;
- (3) 两人轮流走步, 一个玩家不能走步时,游戏结束;
- (4) 游戏的局势不能区分玩家身份, 像围棋这样有黑、白两方的游戏, 就不属于此类 问题。
- ICG 问题有一个特征：给定初始局势, 并且指定先手玩家, 如果双方都采取最优策略, 那么获胜者就已经确定了。也就是说, ICG 问题存在必胜策略。
- 公平组合游戏(Impartial Combinatorial Game, ICG) 是满足以下特征的一类问题:
- 必败态、必胜态
- P-Position（必败态）：当前玩家的先手必败状态
- N-Position（必胜态）：当前玩家的先手必胜状态
Bash游戏
-
问题
- 有 $n$ 颗石子, 甲先取, 乙后取, 每次可以拿 $1 \sim m$ 颗石子, 轮流拿下去, 拿 到最后一颗的人获胜。
-
分析
- (1) 如果 $n %(m+1)=0$, 即 $n$ 是 $m+1$ 的整数倍, 那么不管甲拿多少, 如 $k$ 个, 乙都拿 $m+1-k$ 个, 使剩下的永远是 $m+1$ 的整数倍, 直到最后的 $m+1$ 个, 所以后拿的乙一定赢。
- (2) 如果 $n %(m+1) \neq 0$, 即 $n$ 不是 $m+1$ 的整数倍, 还有余数 $r$, 那么甲拿走 $r$ 个, 剩 下的是 $m+1$ 的倍数, 这样就转移到了情况 (1), 相当于甲乙互换, 结果是甲赢。
-
扩展：如果取石子的数量不是1~m而是只能在一个集合中选择，例如${1,4}$
-
-
如果当前状态经过一步，全部到达必胜态，则当前是状态是必败态。（状态x=5）
-
如果当前状态经过一个，可以到达一个必败态，则当前状态是必胜态。(状态x=6,8)
-
pos的值是周期变化的，周期为5。
-
Nim游戏
-
问题
- 地上有 $n$ 堆石子, 甲、乙两人交替取石子。每人每次只能从任意一堆石子里面 取, 至少取 1 枚, 不能不取。最后没石子可取的人就输了。假如甲是先手, 且已知每堆石子的数量 $a_i$, 问 是否存在先手必胜的策略。
-
结论
- 若初态为必胜态 $\left(a_1 \wedge a_2 \wedge \cdots \wedge a_n \neq 0\right)$ ，则先手必胜;
- 若初态为必败态 $\left(a_1 \wedge a_2 \wedge \cdots \wedge a_n=0\right)$, 则先手必败。
-
定理1：必胜态的后继状态至少存在一个必败态
- 证明:
- 设 $a_1 \wedge \cdots \wedge a_n=s \neq 0$, 设 $s$ 的二进制位为 1 的最高位是第 $k$ 位, 则 $a_1, \cdots, a_n$ 一定有奇数个 $a_i$ 的二进制的第 $\mathrm{k}$ 位为 1 。
用 $a_i{ }^{\wedge} s$ 去替换 $a_i$（因为 $a_i^{\wedge} s<a_i$, 所以是合法的替换）, 则
- 设 $a_1 \wedge \cdots \wedge a_n=s \neq 0$, 设 $s$ 的二进制位为 1 的最高位是第 $k$ 位, 则 $a_1, \cdots, a_n$ 一定有奇数个 $a_i$ 的二进制的第 $\mathrm{k}$ 位为 1 。
$
\begin{aligned}
& a_1{ }^{\wedge} \cdots \wedge a_i{ }^{\wedge} s^{\wedge} \cdots \wedge a_n \
=&a_1 \wedge \cdots^{\wedge} a_i \wedge \cdots \wedge a_n \wedge s \
=&s^{\wedge} s=0
\end{aligned}
$ - 证明:
-
定理2: 必败态的后继状态均为必胜态
- 证明：
- 设 $a_1{ }^{\wedge} \cdots \wedge a_n=0$, 则相同位上 1 的个数为偶数。此时, 无论减少 哪个数, 都会使得异或和 $\neq 0$ 。
- 必胜态与必败态交替出现, 终态 $(0,0, \ldots, 0)$ 是必败态。
- 证明：
-
练习 洛谷 P2197
-
练习 洛谷 P1247
SG函数
TODO