Acwing《算法基础课》第4章 数学知识

文章目录

Acwing《算法基础课》第4章 数学知识质数判断质数分解质因数筛质数朴素筛法埃氏筛法线性筛法 约数求所有约数约数个数定理约数之和定理例子：$12=2^2\times 3^1$，$12$的约数有$1,2,3,4,6,12$，约数之和为$28$，根据公式计算同样是$(2^0+2^1+2^2)\times (3^0+3^1)=28$个 最大公约数 欧拉函数求单个欧拉函数筛法求多个欧拉函数 快速幂扩展欧几里得算法中国剩余定理高斯消元组合数递归法预处理逆元Lucas定理分解质因数法 卡特兰数容斥原理NIM游戏取石子取石子（升级版）

---

质数

判断质数

模板：

bool is_prime(int x) { if (x < 2) return false; for (int i = 2; i <= x / i; i ++ ) // 注意循环条件 if (x % i == 0) return false; return true; }

说明：

试除法判断条件的选择 i < n和i <= n / 2时间复杂度都是$O(n)$，过高i * i <= n虽然时间复杂度是$O(n^{\frac{1}{2}})$，但i * i可能会溢出因此最好的判别条件是i <= n / i，时间复杂度是$O(n^{\frac{1}{2}})$

分解质因数

模板：

void divide(int x) { for (int i = 2; i <= x / i; i ++ ) // 注意循环条件 if (x % i == 0) { int cnt = 0; while (x % i == 0) x /= i, cnt ++ ; cout << i << ' ' << cnt << endl; } if (x > 1) cout << x << ' ' << 1 << endl; // 至多存在一个大于sqrt(n)的质因子 }

说明：

试除法数学知识：$n$最多包含一个大于$\sqrt{n}$的质因子。例如$6=2\times 3$，$\sqrt{6}=2.44949$，存在一个$>\sqrt{6}$的质因子$3$判别质数用i <= n / i条件最好时间复杂度$O(\text{log}n)$，最坏时间复杂度$O(n^{\frac{1}{2}})$

筛质数

朴素筛法

模板：

int primes[N], cnt; // primes[]存储所有素数（静态链表） bool st[N]; // st[x]存储x是否被筛掉 void get_primes(){ for(int i = 2; i <= n; i++){ if (st[i]) continue; if(is_prime[i]) primes[cnt++]=i; //把素数存起来 for(int j = i; j <= n; j += i) //不管是合数还是质数，都用来筛掉后面它的倍数 st[j]=true; } }

说明：

思想：素数的倍数一定不是素数缺点：没必要用合数剔除时间复杂度是$O(n\text{log}n)$

埃氏筛法

模板：

int primes[N], cnt; // primes[]存储所有素数 bool st[N]; // st[x]存储x是否被筛掉 void get_primes(int n) { for (int i = 2; i <= n; i ++ ) { if (!st[i]) { primes[cnt++] = i; // i是当前可用的最小质数，保存到primes中 for (int j = i + i; j <= n; j += i) st[j] = true; // 素数的倍数一定不是素数 } } }

说明：

时间复杂度是$O(n\text{loglog}n)$核心思想：只用质数剔除特点：每次发现的第1个非标记数，一定是质数

线性筛法

模板：

int primes[N], cnt; // primes[]存储所有素数 bool st[N]; // st[x]存储x是否被筛掉 void get_primes(int n) { for (int i = 2; i <= n; i ++ ) { if (!st[i]) primes[cnt ++ ] = i; for (int j = 0; primes[j] <= n / i; j ++ ) { st[primes[j] * i] = true; // 用最小质因子去筛合数primes[j] * i if (i % primes[j] == 0) break; // 若prime[j]是i的最小质因子，则prime[j+1] * i的最小质因子依旧是prime[j] } } }

说明：

核心思想：每个合数必有一个最小素因子，用这个因子筛掉合数理解 当i % primes[j] != 0时，说明此时遍历到的primes[j]不是i的质因子，那么只可能是此时的primes[j] < i的最小质因子，所以primes[j] * i的最小质因子就是primes[j]当有i % primes[j] == 0时，说明i的最小质因子是primes[j]，因此primes[j] * i的最小质因子也就应该是prime[j]，之后接着用st[primes[j+1] * i] = true去筛合数时，就不是用最小质因子去更新了，因为i有最小质因子primes[j] < primes[j+1]，此时的primes[j+1]不是primes[j+1] * i的最小质因子，此时就应该退出循环，避免之后重复进行筛选 时间复杂度是$O(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; }

说明：

试除法求所有约数注意区别因数分解遍历范围是1~sqrt(x)，每次找到约数时，把自身和另一个同时放入最后需要排序，但实际上消耗的时间不多，int最大值才有大约1500个约数

约数个数定理

$n=p_1^{c_1}\times p_2^{c_2}\ast \times ...\times p_k^{c_k}$的约数个数等于 $$(c_1+1)(c_2+1)...(c_k+1)$$ 模板：

unordered_map<int, int> primes; // 用哈希表保存质数的指数 // 质数分解 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 elem : primes) res = res * (elem.second + 1);

说明：

数学原理： 一个整数能唯一展开成若干个质数乘积的形式$n=p_1^{c_1}\times p_2^{c_2}\times ...\times p_k^{c_k}$整数相乘等价于对应质指数相加$n_1\times n_2=(p_1^{a_1}\times p_2^{a_2}\times ...\times p_k^{a_k})\times (p_1^{b_1}\times p_2^{b_2}\times ...\times p_k^{b_k})=p_1^{a_1+b_1}\times p_2^{a_2+b_2}\times ...\times p_k^{a_k+b_k}$ 例子：$12=2^2\times 3^1$，$12$的约数有$1,2,3,4,6,12$共$6$个，根据公式计算同样是$(2+1)\times (1+1)=6$个

约数之和定理

$$sum=\prod _{i=1}^k\sum _{j=0}^{c_i}{p}_i^j=(p_1^0+p_1^1+...+p_1^{c_1})\times ...\times (p_k^0+p_k^1+...+p_k^{c_k})$$

模板：

LL res = 1; for (auto elem : primes) { int p = elem.first, a = elem.second; LL sum = 1; while(a--) sum = sum * p + 1; res *= sum; }

说明：

例子：$12=2^2\times 3^1$，$12$的约数有$1,2,3,4,6,12$，约数之和为$28$，根据公式计算同样是$(2^0+2^1+2^2)\times (3^0+3^1)=28$个

$p^0+p^1+p^2+...+p^n=...((1\times p+1)\times p+1)...$，其中里边迭代n次。因此可直接用结果进行迭代计算，而不用一个变量存储中间值

最大公约数

模板：

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

说明：

欧几里得算法 $\text{gcd}(a, b) = \text{gcd} (b, a\mod b) $$\text{gcd}(a,0)=a$

欧拉函数

$\phi (n)$表示$1$~$n$中与$n$互质的数的个数。 $$\phi \left(n\right)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots \left(1-\frac{1}{p_k}\right)$$ 其中$n=p_1^{c_1}{p}_2^{c_2}\cdots p_k^{c_k}$

求单个欧拉函数

模板：

int phi(int x) { int res = x; for (int i = 2; i <= x / i; i ++ ) if (x % i == 0) { res = res / i * (i - 1); while (x % i == 0) x /= i; } if (x > 1) res = res / x * (x - 1); return res; }

说明：

为避免浮点数除法，编程时采用另一个形式编写代码$\varphi \left( n \right) =n\left( \frac{p_1-1}{p_1} \right) \left( \frac{p_2-1}{p_2} \right) \cdots \left( \frac{p_k-1}{p_k} \right) $可用先除后乘的方式res = res / n * (n-1)避免结果溢出例子：$\phi (6)=2$，因为$1$~$6$中只有$1$和$5$与$6$互质可用容斥原理证明：$\phi \left(n\right)=n-{\sum }_i\frac{n}{p_i}+{\sum }_{i,j}\frac{n}{p_i{p}_j}-{\sum }_{i,j,k}\frac{n}{p_i{p}_j{p}_k}+\cdots$时间复杂度$O(\sqrt{n})$

筛法求多个欧拉函数

模板：

int primes[N], cnt; // primes[]存储所有素数 int euler[N]; // 存储每个数的欧拉函数 bool st[N]; // st[x]存储x是否被筛掉（合数标记） void get_eulers(int n) { euler[1] = 1; for (int i = 2; i <= n; i ++ ) { if (!st[i]) { // 质数 primes[cnt ++ ] = i; euler[i] = i - 1; } for (int j = 0; primes[j] <= n / i; j ++ ) { int t = primes[j] * i; st[t] = true; if (i % primes[j] == 0) { euler[t] = euler[i] * primes[j]; break; } euler[t] = euler[i] * (primes[j] - 1); } } }

说明：

核心思想：$\phi (n)$与$n$的质指数大小无关 当$n$是质数时，$\phi (n)=n-1$当$n\mathrm{m}\mathrm{o}\mathrm{d}p=0$时，$\phi (pn)=p\phi (n)$，因为质数$p$只影响$pn$的质指数$c_p$当$n\mathrm{m}\mathrm{o}\mathrm{d}p\ne 0$时，$\phi (pn)=p\phi (n)(1-\frac{1}{p})=(p-1)\phi (n)$，因为质数$p$影响了$pn$展开项数，多了一项$p^1$ 借助线性筛法求欧拉函数，时间复杂度$O(n)$

快速幂

快速计算$a^k\mathrm{m}\mathrm{o}\mathrm{d}p$

模板：

typedef long long LL; int qmi(int a, int k, int p) { int res = 1; while (k) { if (k & 1) res = (LL) res * a % p; // 防止乘法溢出 a = (LL) a * a % p; // 防止乘法溢出 k >>= 1; } return res; }

说明：

实际上是把$k$表示成二进制$b_{\text{log}k}\cdots b_2{b}_1{b}_0$，因此$k=b_0{2}^{2^0}+b_1{2}^{2^1}+b_2{2}^{2^2}+\cdots b_{\text{log}k}{2}^{2^{\text{log}k}}$计算$a^k\mathrm{m}\mathrm{o}\mathrm{d}p=a^{b_0{2}^{2^0}+b_1{2}^{2^1}+b_2{2}^{2^2}+\cdots b_{\text{log}k}{2}^{2^{\text{log}k}}}\mathrm{m}\mathrm{o}\mathrm{d}p=(a^{b_0{2}^{2^0}}\mathrm{m}\mathrm{o}\mathrm{d}p)\times (a^{b_1{2}^{2^1}}\mathrm{m}\mathrm{o}\mathrm{d}p)\times \cdots \times (a^{b_{\text{log}k}{2}^{2^{\text{log}k}}}\mathrm{m}\mathrm{o}\mathrm{d}p)$此外迭代满足如下关系$2^{2^{i+1}}\mathrm{m}\mathrm{o}\mathrm{d}p=(2^{2^i}\mathrm{m}\mathrm{o}\mathrm{d}p{)}^2$中间结果可能会溢出，要强制进行类型转换时间复杂度$O(\text{log}k)$

扩展欧几里得算法

模板

// 求x, y，使得ax + by = gcd(a, b) int exgcd(int a, int b, int &x, int &y) { if (!b) { x = 1; y = 0; return a; } int d = exgcd(b, a % b, y, x); // 递归结束时，y = x'，x = y' y -= (a/b) * x; // y = x'-(a / b) * y' = y - (a / b) * x return d; } // 详细版 // 求x, y，使得ax + by = gcd(a, b) int exgcd(int a, int b, int &x, int &y) { if (!b) { x = 1; y = 0; return a; } int x_new, y_new; int res = exgcd(b, a % b, x_new, y_new); x = y_new; // x = y' y = x_new - (a/b) * x; // y = x' - (a / b) * y' return res; }

说明：

在计算最大公约数时，顺便求出一组整数解$(x,y)$，使其满足$ax+by=\text{gcd}(a,b)$拓展：方程$ax+by=d$有解的充要条件是$\text{gcd}(a,b)|d$可用于求同余方程$ax\equiv d\left(\mathrm{m}\mathrm{o}\mathrm{d}b\right)\iff \exists y\in \mathrm{Z},s.t.ax+by=d$，但注意，用ex_gcd(a, b, x, y)求得的x不是最终x，因为此时ex_gcd求出的x是满足的$ax+by=\text{gcd}(a,b)$的，而不是满足$ax+by=d$的，二者相差$d/\text{gcd}(a,b)$倍

证明 $$\begin{array}{rl}ax+by& =\mathrm{g}\mathrm{c}\mathrm{d}\left(a,b\right)\\ & =gcd\left(b,a\mathrm{m}\mathrm{o}\mathrm{d}b\right)\\ & =bx\prime +a\mathrm{m}\mathrm{o}\mathrm{d}by\prime \\ & =bx\prime +\left(a-\lfloor \frac{a}{b}\rfloor b\right)y\prime \\ & =bx\prime +ay\prime -\lfloor \frac{a}{b}\rfloor by\prime \\ & =ay\prime +b\left(x\prime -\lfloor \frac{a}{b}\rfloor b\right)\end{array}$$ 对比$a$和$b$的系数得： $$\{\begin{array}{l}x=y\prime \\ y=x\prime -\lfloor \frac{a}{b}\rfloor y\prime \end{array}$$ 因此可根据递归得到的$x\prime$和$y\prime$计算$x$和$y$

中国剩余定理

已知$m_1,m_2\cdots m_k$互质，方程 $$\{\begin{array}{c}x\equiv a_1\left(\mathrm{m}\mathrm{o}\mathrm{d}{m}_1\right)\\ \begin{array}{l}x\equiv a_2\left(\mathrm{m}\mathrm{o}\mathrm{d}{m}_2\right)\\ \cdots \\ x\equiv a_k\left(\mathrm{m}\mathrm{o}\mathrm{d}{m}_k\right)\end{array}\end{array}$$ 的最小正整数解$x=a_{1}M{M}_1^{-1}+a_{2}M{M}_2^{-2}+\cdots a_{k}M{M}_k^{-k}$，其中$M=m_1{m}_2\cdots m_k$，$M_i=\frac{M}{m_i}$，$M_i^{-1}$表示$M_i$模$m_i$的逆元，可通过$M_{i}x\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}{m}_i)$求出

模板

typedef long long LL; // 扩展欧几里得算法 int exgcd(int a, int b, int &x, int &y) { if (!b) { x = 1; y = 0; return a; } int d = exgcd(b, a % b, y, x); // 递归结束时，y = x'，x = y' y -= (a/b) * x; // y = x'-(a / b) * y' = y - (a / b) * x return d; } // 中国剩余定理 LL x = 0, m1, a1; cin >> m1 >> a1; for (int i = 0; i < n - 1; i ++ ) { LL m2, a2; cin >> m2 >> a2; LL k1, k2; LL d = exgcd(m1, -m2, k1, k2); // 求的不是最终解k1和k2 if ((a2 - a1) % d) { x = -1; break; // 无解 } k1 *= (a2 - a1) / d; // 变换成真正的解 int t = m2 / d; // k1 = k1 + k * m2 / d k1 = (k1 % t + t ) % t; // 变换成最小的正整数（防止C++对负数模取余） x = k1 * m1 + a1; // 把两个方程合并成一个方程 LL m = abs(m1 / d * m2); // 变成正数 a1 = k1 * m1 + a1; m1 = m; } if (x != -1) x = (x % m1 + m1) % m1; // 变成最小正整数（防止C++对负数模取余） cout << x << endl;

说明

本质是求解同余方程组如果直接按公式求解，结果可能会溢出，因此采用迭代的方式求解$x\equiv a\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)\iff x=mk+a,k\in \mathrm{Z}$考虑第1个和第2个方程，可得等式$m_1{k}_1+a_1=m_2{k}_2+a_2$，变形得$m_1{k}_1-m_2{k}_2=a_2-a_1$令$d=\text{gcd}(m_1,-m_2)$方程有解的充分必要条件是$d|(a_2-a_1)$不定方程的一个通解是$\{\begin{array}{l}{k}_1=k_1+k\frac{m_2}{d}\\ k_2=k_2+k\frac{m_1}{d}\end{array}$，其中$k$是参数此时$x=k_1{m}_1+a_1=(k_1+k\frac{m_2}{d})m_1+a_1=k_1{m}_1+k\frac{m_1{m}_2}{d}+a_1=k_1{m}_1+a_1+k\frac{m_1{m}_2}{d}=x_1+k{d}_{12}$，这里令$x_1=k_1{m}_1+a_1$，$d_{12}=\frac{m_1{m}_2}{d}$若把$x_1$看成$a_1$，$d_{12}$看成$m_1$，则上式变成$x=a_1+k{m}_1$，即$x\equiv a_1(\mathrm{m}\mathrm{o}\mathrm{d}{m}_1)$，相当于把两个同余方程合并成了一个

高斯消元

模板

// a[N][N+1]是增广矩阵 int gauss() { int c, r; // 按列遍历，化成行阶梯矩阵 for (c = 0, r = 0; c < n; c ++) { // 找到当前列绝对值最大元素所在的行（搜索第r行~最后一行） int t = r; for (int i = r + 1; i < n; i ++ ) if (fabs(a[i][c]) > fabs(a[t][c])) t = i; if (fabs(a[t][c]) < eps) continue; // 当前列全是0 for (int j = c; j <= n; j ++ ) swap(a[t][j], a[r][j]); // 将绝对值最大的行换到最顶端 for (int j = n; j >= c; j -- ) a[r][j] /= a[r][c]; // 将当前上的首位变成1，注意从后往前遍历 for (int i = r + 1; i < n; i ++ ) // 用当前行将下面所有的列消成0 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 2; // 出现0!=0，无解 return 1; // 都是0=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 0; // 有唯一解 }

说明

可在$O(n^3)$求解线性方程组 找到绝对值最大的一行将该行换到最上面将该行第一个数化成$1$把该列下边的数化成$0$ 注意部分过程需要从后往前遍历，否则出现写后读问题

组合数

递归法

$$C_a^b=C_{a-1}^b+C_{a-1}^{b-1}$$

模板

for (int i = 0; i < n; i ++ ) for (int j = 0; j <= i; j ++ ) if (!j) c[i][j] = 1; else c[i][j] = c[i - 1][j] + c[i - 1][j - 1];

说明

意义： $C_a^b$表示从$a$个苹果中选$b$个的方案数i=0时，不会执行else部分，因此不会出现数组越界代码结构有点像杨辉三角适用于询问次数多，但组合数取值范围小的情况（$10^3$数量级）

预处理逆元

假设$m$是一个很大的质数

$(n-1)!$的模$m$逆元是$((n-1)!{)}^{m-2}$

$n!$的模$m$逆元是$(n!{)}^{m-2}$

则$\text{infact}(n)=\text{infact}(n-1)\times \frac{(n!{)}^{m-2}}{((n-1)!{)}^{m-2}}=\text{infact}(n-1)\times n^{m-2}$

其中$n^{m-2}$可通过快速幂求得

模板

// 快速幂模板 int qmi(int a, int k, int p) { int res = 1; while (k) { if (k & 1) res = (LL)res * a % p; a = (LL)a * a % p; k >>= 1; } return res; } // 预处理阶乘的余数和阶乘逆元的余数 fact[0] = infact[0] = 1; for (int i = 1; i < N; i ++ ) { fact[i] = (LL) fact[i - 1] * i % mod; infact[i] = (LL) infact[i - 1] * qmi(i, mod - 2, mod) % mod; }

说明

在涉及乘法运算时，注意先强制转换成long long，然后再取模，否则结果会溢出适用于询问次数多，但组合数取值范围较大的情况（$10^6$数量级）

Lucas定理

若$p$是质数，则对于任意整数 $1\le m\le n$，有： $$C_n^m=C_{n\mathrm{m}\mathrm{o}\mathrm{d}p}^{m\mathrm{m}\mathrm{o}\mathrm{d}p}\times C_{n÷p}^{m÷p}\mathrm{m}\mathrm{o}\mathrm{d}p$$

模板

// 快速幂模板 int qmi(int a, int k) { int res = 1; while (k) { if (k & 1) res = (LL)res * a % p; a = (LL)a * a % p; k >>= 1; } return res; } // 通过定理求组合数C(a, b) int C(int a, int b) { int res = 1; for (int i = 1, j = a; i <= b; i ++, j -- ) { res = (LL)res * j % p; // 构造分子a * (a - 1) * ... * (a - b + 1) res = (LL)res * qmi(i, p - 2) % p; // 构造(b!)的逆元(b!)^{p-2} } return res; } int lucas(LL a, LL b) { if (a < p && b < p) return C(a, b); return (LL)C(a % p, b % p) * lucas(a / p, b / p) % p; }

说明

适用于询问次数少，但组合数取值范围较大的情况（$a,b\le 10^{18}$，$p\le 10^5$）两方面优化组合数的求解 快速幂加速计算小规模组合数卢卡斯定理降低组合数的规模 注意变量类型以及输入输出的类型是int还是long long

分解质因数法

模板

int primes[N], cnt; // 存储所有质数 int sum[N]; // 存储每个质数的次数 bool st[N]; // 存储每个数是否已被筛掉（合数标记） // 线性筛法求素数 void get_primes(int n) { for (int i = 2; i <= n; i ++ ) { if (!st[i]) primes[cnt ++ ] = i; for (int j = 0; primes[j] <= n / i; j ++ ) { st[primes[j] * i] = true; if (i % primes[j] == 0) break; } } } // 求n！质因数分解后，在质数p的次数 int get(int n, int p) { int res = 0; while (n) { res += n / p; n /= p; } return res; } // 高精度乘低精度模板 vector<int> mul(vector<int> a, int b) { vector<int> c; int t = 0; for (int i = 0; i < a.size(); i ++ ) { t += a[i] * b; c.push_back(t % 10); t /= 10; } while (t) { c.push_back(t % 10); t /= 10; } return c; } get_primes(a); // 预处理范围内的所有质数 for (int i = 0; i < cnt; i ++ ) // 求每个质因数的次数 { int p = primes[i]; sum[i] = get(a, p) - get(b, p) - get(a - b, p); } vector<int> res; res.push_back(1); for (int i = 0; i < cnt; i ++ ) // 用高精度乘法将所有质因子相乘 for (int j = 0; j < sum[i]; j ++ ) res = mul(res, primes[i]);

说明

本质是质因数分解+高精度乘法适用求真实值，而非取余后的结果主要思想 线性筛法找出$2$~$a$内的所有质数依次遍历质数，求出组合数在各个质数的次数（通过get方法计算）高精度乘法计算各个质因子的乘积 get(int n, int p)求n!质因数分解在$p$的次数的数学公式$\lfloor \frac{n}{p} \rfloor +\lfloor \frac{n}{p^2} \rfloor +\lfloor \frac{n}{p^3} \rfloor +\cdots $

卡特兰数

$\text{catalan}(n)=\frac{C_{2n}^n}{n+1}$

容斥原理

$$\left|\bigcup _{k=1}^n{S}_k\right|=\sum _i\left|S_i\right|-\sum _{i,j}\left|S_i\cap S_j\right|+\sum _{i,j,k}\left|S_i\cap S_j\cap S_k\right|-\cdots$$

$$C_n^1+C_n^2+C_n^3+\cdots +C_n^n=2^n-C_n^0=2^n-1$$

模板

int res = 0; // 一共有2^m-1种集合 for (int i = 1; i < 1 << m; i ++ ) { int t = 1, s = 0; // t表示当前集合的乘积，s表示符号（正负交替） // 遍历每种集合 for (int j = 0; j < m; j ++ ) if (i >> j & 1) { // 元素存在 if ((LL)t * p[j] > n) { t = -1; // 构造的质数乘积比n大，舍弃 break; } t *= p[j]; s ++ ; } if (t != -1) { if (s % 2) res += n / t; // 根据s的奇偶性实现正负交替 else res -= n / t; } }

说明

$2^m$可以用1 << m实现

m个元素可以构造$2^m-1$种不同的非空集合，集合包含的元素可用$m$位二进制表示，例如5=101b，表示集合有第1个元素和第3个元素

对于每个元素都有$C_n^1-C_n^2+C_n^3-\cdots +{\left(-1\right)}^{k-1}{C}_n^n=1$，即每个元素取到的次数都是1，不重复

$1$~$n$中能被$p$整除的数的个数为$\lfloor \frac{n}{p} \rfloor $

遍历的次序与公式不太一样，不是先加$m$个数，再减去$C_m^2$个数。实际上，当集合元素个数是奇数时，符号为正，反之为负。因此可根据集合个数的奇偶性判断符号的正负

模板是基于整除个数问题设计的

时间复杂度为$O(2^n)$

NIM游戏

公平组合游戏ICG 若一个游戏满足以下条件，则称该游戏为一个公平组合游戏。

由两名玩家交替行动；在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关；不能行动的玩家判负；

NIM博弈属于公平组合游戏，但城建的棋类游戏，比如围棋，就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子，胜负判定也比较复杂，不满足条件2和条件3。

取石子

给定N堆物品，第$i$堆物品有$A_i$个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可把一堆取光，但不能不取。取走最后一件物品者获胜。两人都采取最优策略，问先手是否必胜。

定义

我们把这种游戏称为NIM博弈。把游戏过程中面临的状态称为局面。整局游戏第一个行动的称为先手，第二个行动的称为后手。若在某一局面下无论采取何种行动，都会输掉游戏，则称该局面必败。 所谓采取最优策略是指，若在某一局面下存在某种行动，使得行动后对面面临必败局面，则优先采取该行动。同时，这样的局面被称为必胜。我们讨论的博弈问题一般都只考虑理想情况，即两人均无失误，都采取最优策略行动时游戏的结果。 NIM博弈不存在平局，只有先手必胜和先手必败两种情况。

必胜状态，先手进行某一个操作，留给后手是一个必败状态时，对于先手来说是一个必胜状态。即先手可以走到某一个必败状态。 必败状态，先手无论如何操作，留给后手都是一个必胜状态时，对于先手来说是一个必败状态。即先手走不到任何一个必败状态。

定理

NIM博弈先手必胜，当且仅当$A_1\oplus A_2\oplus \cdots \oplus A_n\ne 0$

性质

操作到最后时，每堆石子数都是0，$0\oplus 0\oplus \cdots \oplus 0=0$在操作过程中，如果 $A_1\oplus A_2\oplus \cdots \oplus A_n=x\ne 0$。那么玩家必然可以通过拿走某一堆若干个石子将异或结果变为0。在操作过程中，如果 $A_1\oplus A_2\oplus \cdots \oplus A_n=0$，那么无论玩家怎么拿，必然会导致最终异或结果不为$0$

性质证明

性质2的证明：不妨设$x$的二进制表示中最高一位$1$在第$k$位，那么在$A_1,A_2,\cdots ,A_n$中，必然有一个数$A_i$，它的第$k$为时$1$，且$A_i\oplus x<A_i$，那么从第$i$堆石子中拿走$A_i-A_i\oplus x$个石子，第ii堆石子还剩$A_i-\left( A_i-A_i\oplus x \right) $，此时$A_1\oplus A_2\oplus \cdots \oplus A_i\oplus x\oplus \cdots \oplus A_n=x\oplus x=0$性质3的证明：反证法：假设玩家从第$i$堆石子拿走若干个，结果仍是$0$。不妨设还剩下$A_i\prime$个，因为不能不拿，所以$0\le A_i\prime <A_i$，且$A_1\oplus A_2\oplus \cdots \oplus A_i\prime \oplus \cdots \oplus A_n=0$。那么$\left(A_1\oplus A_2\oplus \cdots \oplus A_i\oplus \cdots \oplus A_n\right)\oplus \left(A_1\oplus A_2\oplus \cdots \oplus A_i\prime \oplus \cdots \oplus A_n\right)=A_i\oplus A_i\prime =0$，则 $A_i=A_i\prime$，与假设$0\le A_i\prime <A_i$矛盾。

分析

当先手面对的局面是$A_1\oplus A_2\oplus \cdots \oplus A_n\ne 0$，则先手总有办法让后手局面变成$A_1\oplus A_2\oplus \cdots \oplus A_n=0$，后手必败，先手必赢当先手面对的局面是$A_1\oplus A_2\oplus \cdots \oplus A_n=0$，则后手总有办法让先手局面变成$A_1\oplus A_2\oplus \cdots \oplus A_n\ne 0$，先手必败，后手必赢

取石子（升级版）

约束条件

每次可拿石子的个数不是任意的，而是集合$S$中的元素

概念

$\text{mex}$

$\text{mex(S)}$表示不属于集合$S$的最小自然数，即$\text{mex}(S)=\min \left{ x \mid x\notin S\land x\in \mathrm{N} \right} $。

例如当$S=1,2$时，$\text{mex}(S)=0$例如当$S=0,2$时，$\text{mex}(S)=1$

有向图游戏

给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。

任何一个公平组合游戏都可以转化为有向图游戏。具体方法是，把每个局面看成图中的一个节点，并且从每个局面向沿着合法行动能够到达的下一个局面连有向边。

$\text{SG}$

在有向图游戏中，对于每个节点$x$，设从$x$出发共有$k$条有向边，分别到达节点$y_1,y_2,\cdots ,y_k$，定义$\text{SG}(x)$为$x$的后继节点$y_1,y_2,\cdots ,y_k$的$\text{SG}$函数值构成的集合再执行$\text{mex}(S)$运算的结果，即： $$\text{SG}(x)=\text{mex}(\text{SG}(y1),\text{SG}(y2),\cdots ,\text{SG}(yk))$$ 特别地，整个有向图游戏$G$的$\text{SG}$函数值被定义为有向图游戏起点$s$的$\text{SG}$函数值，即$\text{SG}(G)=\text{SG}(s)$。

有向图游戏的和

设$G_1,G_2,\cdots ,G_m$是$m$个有向图游戏。定义有向图游戏$G$，它的行动规则是任选某个有向图游戏$G_i$，并在$G_i$上行动一步。$G$被称为有向图游戏$G_1,G_2,\cdots ,G_m$的和。 有向图游戏的和的SG函数值等于它包含的各个子游戏SG函数值的异或和，即： $$\mathrm{S}\mathrm{G}\left(G\right)=\mathrm{S}\mathrm{G}\left(G_1\right)\oplus \mathrm{S}\mathrm{G}\left(G_2\right)\oplus \cdots \oplus \mathrm{S}\mathrm{G}\left(G_m\right)$$

性质

$\text{SG}(k)有$$k$个后继结点，分别是$0$~$k-1$非$0$可以走向$0$$0$只能走向非$0$

性质证明

类似NIM游戏的证明

定理

有向图游戏的某个局面必胜，当且仅当该局面对应节点的SG函数值大于$0$。 有向图游戏的某个局面必败，当且仅当该局面对应节点的SG函数值等于$0$。

模板

int s[N], f[M]; memset(f, -1, sizeof f); // 初始化 // 记忆化搜索（备忘录法） int sg(int x) { if (f[x] != -1) return f[x]; // 已经计算过 // 构造子树 unordered_set<int> S; for (int i = 0; i < m; i ++ ) { int sum = s[i]; if (x >= sum) S.insert(sg(x - sum)); // 保存后继结点到S中（递归） } // mem(x) for (int i = 0; ; i ++ ) if (!S.count(i)) return f[x] = i; } // 把n堆石子看成n个独立的有向图G，把各个有向图结果做异或即可得到答案 int x, res = 0; for (int i = 0; i < n; i ++ ) { cin >> x; res ^= sg(x); }

---

P.S. 部分内容来自y总的模板 如果大家有兴趣，可以去Acwing《算法基础课》看看 我在Acwing也分享了一份，欢迎去围观