基础数学知识

博主： RearWaves
发布时间：2023 年 04 月 23 日
353 次浏览
暂无评论
15095字数
分类：算法设计

# 数学知识1

> **特别声明:** 本博客是我在学习[acwing网站](https://www.acwing.com/)中的算法课程中所记录的笔记, 部分资源来源于网络, 如果有侵权,请及时联系作者删除相关的部分.
> 
> 如果有错误可以私信作者(qq:**1351798781**)进行更改, 非常感谢.
> 
> 欢迎够买[正版ACwing课程](https://www.acwing.com/activity)(不是广告, ACwing没有打钱).

# 1 质数

1. 质数和合数是针对所有大于1的 “自然数” 来定义的(所有小于等于1的数都不是质数).
2. 所有小于等于1的整数既不是质数也不是合数.
3. 质数和素数都是同一种性质,只是叫法不同.

## 1.1 试除法

### [866. 试除法判定质数](https://www.acwing.com/problem/content/868/)

给定 n 个正整数 ai, 判定每个数是否是质数.

一个合数的约数总是成对出现的,如果d|n,那么(n/d)|n,因此我们判断一个数是否为质数的时候,只需要判断较小的那一个数能否整除n就行了,即只需枚举**d<=(n/d)**,即dd<=n,d<=sqrt(n)就行了.

sqrt(n)这个函数执行的时候比较慢.

算法复杂度O(sqrt(n)).

```c++
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;
}
int main() {
	int n;
	cin >> n;
	while (n--) {
		int x;
		cin >> x;
		if (is_prime(x)) puts("Yes");
		else puts("No");
	}
	return 0;
}
```

### [867. 分解质因数](https://www.acwing.com/problem/content/869/)

用到的原理:唯一分解定理(算数基本定理))

一个合数分解而成的质因数最多只包含一个大于sqrt(n)的质因数(反证法,若n可以被分解成两个大于sqrt(n)的质因数,则这两个质因数相乘的结果大于n,与事实矛盾).

当枚举到某一个数i的时候,n的因子里面已经不包含2-i-1里面的数,如果n%i==0,则i的因子里面也已经不包含2-i-1里面的数,因此每次枚举的数都是质数.

算数基本定理(唯一分解定理):任何一个大于1的自然数N,如果N不为质数,那么N可以唯一分解成有限个质数的乘积$N=P_1^{a_1}P_2^{a_2}P_3^{a_3}\cdots P_n^{a_n}$, 这里$P_1<P_2<P_3<\cdots <P_n$均为质数, 其中指数ai是正整数.

算法复杂度O(sqrt(n)).最好log(n).

```c++
void divide(int x) {
	for (int i = 2; i <= x / i; i++) {
		if (x % i == 0) {
			int s = 0;
			while (x % i == 0) x /= i, s++;
			cout << i << ' ' << s << endl;
		}
	}
	if (x > 1) cout << x << ' ' << 1 << endl;
	cout << endl;
}
int main()
{
	int n;
	cin >> n;
	while (n--) {
		int x;
		cin >> x;
		divide(x);
	}
	return 0;
}
```

## 1.2 筛质数

做法:把2~(n-1)中的所有的数的倍数都标记上,最后没有被标记的数就是质数.

原理:假定有一个数p未被2~(p-1)中的数标记过,那么说明,不存在2~(p-1)中的任何一个数的倍数是p,也就是说p不是2~(p-1)中的任何数的倍数,也就是说2~(p-1)中不存在p的约数,因此,根据质数的定义可知:p是质数.

时间复杂度:约为O(nlogn);(注:此处的log数特指以2为底的log数).调和级数:当n趋近于正无穷的时候,$\frac12+\frac13+\frac14+\frac15+…+\frac1n=ln\ n+c$.(c是欧阳常数,约等于0.577左右.).

### [868. 筛质数](https://www.acwing.com/problem/content/870/)

给定一个正整数 n, 请你求出 1∼n 中质数的个数.

**埃氏筛法(稍加优化版的筛法)**

质数定理:1~n中有n/ln n个质数.

原理:在朴素筛法的过程中只用质数项去筛.

时间复杂度:粗略估计:O(n).实际:O(nlog(logn)).1~n中,只计算质数项的话,"$\frac12+\frac13+\frac14+\frac15+…+\frac1n$"的大小约为log(logn).

```c++
const int N = 1e6 + 10;
int primes[N], cnt;
bool st[N];
void get_primes(int n) {
	for (int i = 2; i <= n; i++) {
		if (st[i]) continue;
		primes[cnt++] = i;
		for (int j = i + i; j <= n; j += i)
			st[j] = true;
	}
}
int main() {
	int n;
	cin >> n;
	get_primes(n);
	cout << cnt << endl;
	return 0;
}
```

**线性筛法**

若n在10的6次方的话,线性筛和埃氏筛的时间效率差不多,若n在10的7次方的话,线性筛会比埃氏筛快了大概一倍.

核心:1~n内的合数p只会被其最小质因子筛掉.

原理:1~n之内的任何一个合数一定会被筛掉,而且筛的时候只用最小质因子来筛,然后每一个数都只有一个最小质因子,因此每个数都只会被筛一次,因此线性筛法是线性的.

关于for循环的解释:我们枚举的时候是从小到大枚举的所有质数

1. 当i%primes[j]=0时,因为是从小到大枚举的所有质数,所以primes[j]就是i的最小质因子,而primes[j]又是其本身primes[j]的最小质因子,因此当i%primes[j]=0时,primes[j]是primes[j]*i的最小质因子.
2. 当i%primes[j]!=0时,因为是从小到大枚举的所有质数,且此时并没有出现过有质数满足i%primes[j]=0,因此此时的primes[j]一定小于i的最小质因子,而primes[j]又是其本身primes[j]的最小质因子,所以当i%primes[j]!=0时,primes[j]也是primes[j]*i的最小质因子.
3. 综合1,2得知,在内层for循环里面无论何时,primes[j]都是primes[j]*i的最小质因子,因此”st[primes[j]i]=true”语句就是用primes[j]i这个数的最小质因子来筛掉这个数.

这个算法我们需要注意的是它始终筛的是i * prime[j]这个数, 且prime[j]是从小到大枚举的. 那么若prime[j]能整除i, prime[j]当然能整除i * prime[j], 则对于i * prime[j]来说, 它已经被最小质因子prime[j]筛掉了, break掉即可. 就算prime走到了最后一个位置,  i都不能被整除, 那说明i * prime[j]的最小质因子是新加进来的prime[cnt]. 无论如何. i * prime[j]都是被最小质因子筛掉的. 而任何一个合数k=i×k=i×它的最小质因子, 都会在遍历到i这一步被筛掉, 所以不用担心漏筛的问题.

```c++
const int N = 1e6 + 10;
int primes[N], cnt;
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;
		}
	}
}
int main() {
	int n;
	cin >> n;
	get_primes(n);
	cout << cnt << endl;
	return 0;
}
```

# 2 约数

## 2.1 约数的性质

### [869. 试除法求约数](https://www.acwing.com/problem/content/871/)

给定 n 个正整数 ai, 对于每个整数 ai, 请你按照从小到大的顺序输出它的所有约数.

```c++
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;
}
int main() {
	int n;
	cin >> n;
	while (n--) {
		int x;
		cin >> x;
		auto res = get_divisors(x);
		for (auto x : res) cout << x << ' ';
		cout << endl;
	}
	return 0;
}
```

$n = p_1^{\alpha_1} * p_2^{\alpha_2} *\dots * p_k^{\alpha_k}$,则其约数的个数为:$ans = (\alpha_1+1)(\alpha_2+1)\dots(\alpha_k+1)$
因为 任何一个 约数 d 可以表示成
$d=p_1^{\beta_1} * p_2^{\beta_2} * \dots * p_k^{\beta_k},0\leq\beta_i\leq\alpha_i$
每一项的 $\beta_i$ 如果不同, 那么约数 d 就不相同(算数基本定理, 每个数的因式分解是唯一的)所以n的约数就跟 $\beta_i$ 的选法是一一对应的.

$\beta_1$ 一共有 $0\sim\alpha_1$ 种选法,$\beta_2$ 一共有 $0\sim\alpha_2$ 种选法,$\dots$,$\beta_k$ 一共有 $0\sim\alpha_k$ 种选法.

由乘法原理, 一共有 ans 个约数.int 范围内约数最多的数的个数为 15361536, 那个数为 1745944200.

约数之和为:$(p_1^0 + p_1^1 + p_2^2 +…+ p_1^{\alpha_1})(p_2^0 + p_2^1 + p_2^2 +…+ p_2^{\alpha_2})…(p_k^0 + p_k^1 + p_k^2 +…+ p_k^{\alpha_k})$

### [870. 约数个数](https://www.acwing.com/problem/content/872/)

给定 n 个正整数 ai, 请你输出这些数的乘积的约数个数, 答案对 10^9+7 取模.

$N=\prod_{i=1}^{k} p_{i}^{a_{i}}=p_{1}^{a_{1}} \cdot p_{2}^{a_{2}} \ldots p_{k}^{a_{k}}$

约数个数:  $\prod_{i=1}^{k}\left(a_{i}+1\right)=\left(a_{1}+1\right)\left(a_{2}+1\right) \ldots\left(a_{k}+1\right)$

```c++
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;
}
```

### [871. 约数之和](https://www.acwing.com/problem/content/description/873/)

给定 n 个正整数 ai, 请你输出这些数的乘积的约数个数, 答案对 10^9+7 取模.

$N=\prod_{i=1}^{k} p_{i}^{a_{i}}=p_{1}^{a_{1}} \cdot p_{2}^{a_{2}} \ldots p_{k}^{a_{k}}$

约数之和:

$$
\begin{aligned}
\prod_{i=1}^{k} \sum_{j=0}^{a i} p_{i}^{j} & =\prod_{i=1}^{k}\left(p_{i}^{0}+p_{i}^{1}+\ldots+p_{i}^{a i}\right) \\
& =\left(p_{1}^{0}+p_{1}^{1}+\ldots+p_{1}^{a_{1}}\right)\left(p_{2}^{0}+p_{2}^{1}+\ldots+p_{2}^{a_{2}}\right) \ldots\left(p_{k}^{0}+p_{k}^{1}+\ldots+p_{k}^{a_{k}}\right)
\end{aligned}
$$

如何求 $S(n)=x^0+x^1+x^2+…+x^n$, $S(n)=1+x×(x^0+x^1+…+x^{n−1})=1+S(n−1)×x$, 边界情况S(0)=1, 所以可以令t=1, 乘以x再加上1得到S(1), 再乘以x并加上1得到S(2),执行n次循环得到S(n).

```c++
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;
}
```

## 2.2 最大公约数

在库algorithm中提供了求最大公约数的方法, 具体使用方法是__gcd(a, b) 即返回了ab的最大公约数.

```c++
int main() {
    int t;
    cin >> t;
    while(t--) {
        int a, b;
        cin >> a >> b;
        cout << __gcd(a, b);
    }
}
```

**辗转相除法**

求两个正整数 a 和 b 的 最大公约数 d 则有 gcd(a,b) = gcd(b,a%b).

### [872. 最大公约数](https://www.acwing.com/problem/content/874/)

给定 n 对正整数 ai,bi, 请你求出每对数的最大公约数.

```c++
int gcd(int a, int b) {
	return b ? gcd(b, a % b) : a;
}
int main() {
	int n;
	cin >> n;
	while (n--) {
		int a, b;
		scanf("%d%d", &a, &b);
		printf("%d\n", gcd(a, b));
	}
	return 0;
}
```

# 3 欧拉函数

**欧拉函数的定义:**

> 1∼N 中与 N 互质的数的个数被称为欧拉函数, 记为 ϕ(N).
> 
> 若在算数基本定理中, $N=p^{a_1}_1p^{a_2}_2 \cdots p^{a_m}_m$, 则：
> $ϕ(N) = N×\frac{p_1−1}{p_1}×\frac{p_2−1}{p_2}×\cdots ×\frac{p_m−1}{p_m}$.

**求解方法一:**

首先,  欧拉函数是一个积性函数, 当m,n互质时, $φ(mn)=φ(m)∗φ(n)$.

根据唯一分解定理知 $n=p^{a_1}_1 \times p^{a_2}_2 \times \cdots p^{a_x}_x$, 因此 $φ(n)=φ(p^{a_1}_1)\times \cdots \times φ(p^{a_x}_x)$.

对于任意一项: $φ(p^{a_s}_s)=p^{a_s}_s−p^{(a_s−1)}_s$, 从定义出发 $φ(p^{a_s}_s)$等于小于或等于$p^{a_s}_s$的正整数中与$p^{a_s}_s$互质的数的数目.

从1到$p^{a_s}_s$中共有$p^{a_s}_s$个数字, 其中与$p^{a_s}_s$不互质的有$p_s,2p_s,\cdots ,p_s^{a_s−1}\times p_s$ ,共$p_s^{a_s−1}$项, 所以 $φ(p^{a_s}_s) = p^{a_s}_s - p_s^{a_s−1}=p^{a_s}_s\times (1−\frac{1}{p_s})$.

因此

$$
\begin{align}
φ(n)& =φ(p^{a_1}_1)\times \cdots \times φ(p^{a_x}_x) \\
& =(p^{a_1}_1−p_1^{a_1−1})\times \cdots \times(p^{a_x}_x−p_x^{a_x−1}) \\
& =p^{a_1}_1\times (1−\frac1{p_1})\times p^{a_2}_2\times (1−\frac1{p_2})\times \cdots \times p^{a_x}_x\times (1−\frac1{p_x}) \\
& =p^{a_1}_1\times p^{a_2}_2\times \cdots \times p^{a_x}_x\times (1−\frac1{p_1})\times (1−\frac2{p_2})\times \cdots \times(1−\frac x{p_x}) \\
& =n \times \prod \limits_{i=1}^x (1-\frac1{p_i}) \\
\end{align}
$$

**求解方法二:**

容斥原理: 设n=p_1^{α_1}×p_2^{α_2}×…×pkαk

要求与n互质的数的个数, 可以减去所有$p_1,p_2\cdots p_k$的倍数, 观察可知既是$p_1,p_2$的倍数被$p_1,p_2$的倍数减了两次, 所以要加1次$p_1×p_2$等由$p_i×p_j$组成的数, 可又能发现$p_i×p_j×p_k$组成的数算了0次, 得加1次, 以此类推, 我们可以发现：

$$
\begin{align}
φ(n)=&n−(\frac n{p_1}+\frac n{p_2}+\cdots +\frac n{p_k}) \\
&+(\frac n{p_1×p_1}+\frac n{p_1×p_2}+\cdots +\frac n{p_k×p_k})\\
&−(\frac n{p_1×p_1×p_1}+\frac n{p_1×p_1×p_2}\cdots +\frac n{p_k×p_k×p_k})\\
&\cdots
\end{align}
$$

以此类推, 公式$φ(n)=n×(1−\frac1{p_1})×(1−\frac1{p_2})×\cdots ×(1−\frac1{p_k})$展开后可得以上算式.

算法时间复杂度: $O(n\times \sqrt{a})$

### [873. 欧拉函数](https://www.acwing.com/problem/content/875/)

给定 n 个正整数 ai, 请你求出每个数的欧拉函数.

```c++
int phi(int x) {
	int res = x;
	for (int i = 2; i <= x / i; i++) {
		if (x % i == 0) {
			//这个地方不能使用1-i/1,否则会出现小数
			res = res / i * (i - 1);
			while (x % i == 0) x /= i;
		}
	}
	if (x > 1) res = res / x * (x - 1);
	return res;
}
int main() {
	int n;
	cin >> n;
	while (n--) {
		int x;
		cin >> x;
		cout << phi(x) << endl;
	}
	return 0;
}
```

### [874. 筛法求欧拉函数](https://www.acwing.com/problem/content/876/)

给定一个正整数 n, 求 1∼n 中每个数的欧拉函数之和.

**解题思路:**

先写出线性筛算法的模板. 考虑特殊情况：若该数是质数p的话, 那么该数的欧拉函数就是p−1.

需要注意的是: 每个数的欧拉函数与质因子的次数无关. 例如：$N=2^{100}×3^{100}$, 但是N的欧拉函数还是$N×(1−\frac12)×(1−\frac13)$.

若$i\ mod\ primes[j]=0$, 由于primes[j]是i的一个质因子, 并且在计算i的欧拉函数的时候已经计算了primes[j]出现的情况$(1−\frac1{primes[j]})$, 所以$φ(primes[j]×i)=primes[j]×φ(i)$.

若$i\ mod\ primes[j]\ne 0$, primes[j]就一定是primes[j]×i的最小质因子, 而且primes[j]不包含在ii的质因子当中. 由于$φ(i)=i×(1−\frac1{p_1})×(1−\frac1{p_2})×\cdots ×(1−\frac1{p_k})$, 所以$φ(primes[j]×i)=primes[j]×i×(1−\frac1{p_1})×(1−\frac1{p_2})×\cdots ×(1−\frac1{p_k})×(1−\frac1{primes[j]})$. 最终就可以得到$φ(primes[j]×i)=primes[j]×φ(i)×(1−\frac1{primes[j]})=φ(i)×(primes[j]−1)$.

时间复杂度: O(n).

```c++
const int N = 1e6 + 10;
//筛选质数 primes[]存放已经找到的质数, cnt记录已经找到的质数数量
int primes[N], cnt; 
int phi[N];
bool st[N];		//标记某个数是不是质数

ll get_eulers(int n) {
	phi[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (!st[i]) {
			primes[cnt++] = i;
			phi[i] = i - 1;	//质数p的欧拉函数是p-1
		}
		for (int j = 0; primes[j] <= n / i; j++) {
			st[primes[j] * i] = true;
			//当p[j]是i的一个约数时, i的质因数与p[j] * i的质因数完全相同. 
			if (i % primes[j] == 0) {
				phi[primes[j] * i] = phi[i] * primes[j];
				break;
			}
			//当p[j]不是i的约数, i与i*p[j]的质因子相差一个p[j]
			phi[primes[j] * i] = phi[i] * (primes[j] - 1);
		}
	}
	ll res = 0;
	for (int i = 1; i <= n; i++) res += phi[i];
	return res;
}
int main() {
	int n;
	cin >> n;
	cout << get_eulers(n) << endl;
	return 0;
}
```

**应用: 欧拉定理：设  m  是大于1的正整数, 如果整数 a 与 m 互素, 那么$a^{φ(m)}≡1(mod m)$.**

证明: 设集合 $A= { x_1(mod\ m),x_2(mod\ m),\cdots,x_{φ(m)}(mod\ m) }$ 是小于 m 的所有与 m 互素的不同的数的集合(这里取模是为了与后面形式上同一, 不取模肯定也是小于 m 的). 然后再令 $B= { ax_1(mod\ m),ax_2(mod\ m),\cdots,ax_{φ(m)}(mod\ m) }$.

因为都取了模, 所以 B 中所有元素也是小于 m 的. 又因为 a 与 m 互素, 每一个 x 都与 m 互素, 由互素的性质可以得到$ax_1, ax_2,…,ax_m$ 都与 m 互素, 即$(ax_i,m)=1,i=1,2,…,m$.

我们还可以进一步说明, B 中所有的元素两两不同, 若 B 中存在相同的元素, 即假设存在$ax_i(mod\ m)=ax_j(mod\ m)⟺ax_i≡ax_j(mod\ m)$,那么因为 a 与 m 是互素的, 所以 a 可以直接约掉, 那么就会有i≠j, 有$ax_i(mod\ m)=ax_j(mod\ m)⟺ax_i≡ax_j(mod\ m)$.这就与A集合中元素互不相同这一前提出现了矛盾.

所以 B 中元素也互不相同且和 m 互素, 并且 A 集合 与 B 集合元素的个数是相等的, 那么 B 中的这些元素肯定也是 A 中这些元素, 这不过是顺序换了一下, 专业术语叫做集合 A 元素的一个置换.

那么把集合 A 内所有元素相乘与 B 内所有元素相乘是相等的, 即$x_1x_2\cdots x_{φ(m)}≡ax_1ax_2\cdots ax_{φ(m)}(mod\ m)$, 即$x_1x_2\cdots x_{φ(m)}≡a^{φ(m)}x_1x_2\cdots x_{φ(m)}(mod\ m)$.

所以$a^{φ(m)}≡1(mod\ m)$.

**费马定理: $a^{p-1}≡1(mod\ p)$.**

# 4 快速幂

预处理出$a^{2^0},a^{2^1},a^{2^2},\cdots ,a^{2^{log\ b}}$这b个数.

将$a^b$用$a^{2^0},a^{2^1},a^{2^2},\cdots ,a^{2^{log\ b}}$这b种数来组合,即组合成$a^b=a^{2^{x_1}}×a^{2^{x_2}}×\cdots ×a^{2^{x_t}}=a^{2^{x_1}}+a^{2^{x_2}}+\cdots +a^{2^{x_t}}$, 即用二进制表示.

二进制可以表示所有数,且用单一用二进制表示时,b单一表示最大可表示为二进制形式的$2^{log\ b}$.

### [875. 快速幂](https://www.acwing.com/problem/content/877/)

给定 n 组 ai,bi,pi, 对于每组数据, 求出 $a^{b_i}_i\ mod\ p_i$ 的值.

```c++
int qmi(int a, int b, int p) {
	int res = 1;
	while (b) {	//对b进行二进制化,从低位到高位
		//如果b的二进制表示的第0位为1,则乘上当前的a
		if (b & 1) res = (LL)res * a % p;
		b >>= 1;	//b右移一位
		//更新a,a依次为a^{2^0},a^{2^1},a^{2^2},....,a^{2^logb}
		a = (LL)a * a % p;
	}
	return res;
}
int main() {
	int n;
	scanf("%d", &n);
	while (n--) {
		int a, b, p;
		scanf("%d%d%d", &a, &b, &p);
		printf("%d\n", qmi(a, b, p));
	}
	return 0;
}
```

### [876. 快速幂求逆元](https://www.acwing.com/problem/content/878/)

给定 n 组 ai,pi, 其中 pi 是质数, 求 ai 模 pi 的乘法逆元, 若逆元不存在则输出 `impossible`.

**注意**：请返回在 0∼p−1 之间的逆元.

### 乘法逆元的定义

> 若整数 b, m 互质, 并且对于任意的整数 a, 如果满足 b|a, 则存在一个整数 x, 使得 $a/b≡a×x(mod\ m)$, 则称 x 为 b 的模 m 乘法逆元, 记为 $b^{−1}(mod\ m)$.
> 
> b 存在乘法逆元的充要条件是 b 与模数 m 互质. 当模数 m 为质数时, $b^{m−2}$ 即为 b 的乘法逆元.

**当m为质数时**, 求解过程如下:

由费马小定理可知: bm−1≡1modm, 而a/b≡a∗xmodm. 得: a/b∗bm−1≡a∗xmodm. 即为a∗bm−2≡a∗xmodm.

而b|a,且b与m互质,因此对于b来说,一定存在一个a也与m互质,故而a可以在两边同时约去. 因此x≡bm−2modm.

无解条件 即 b与m不互质时无解,而m为质数,所以b只能为m的倍数, 此时无解,也就是b%m==0.

**当m不是质数时**, 则需要用扩展欧几里得求逆元.

**逆元的作用**: 当 a,b 很大时 求 $a/b\ mod\ p$ 的值. 而$a/b\ mod\ p≠((a\ mod\ p)/(b\ mod\ p))mod\ p$, 因此可以借助逆元转化为乘法,再算,设b的逆元为b−1,则 $a/b\ mod\ p=a∗b−1\ mod\ p=((a\ mod\ p)∗(b−1\ mod\ p))mod\ p$.

```c++
int qmi(int a, int b, int p) {
	int res = 1;
	while (b) {	//对b进行二进制化,从低位到高位
		//如果b的二进制表示的第0位为1,则乘上当前的a
		if (b & 1) res = (LL)res * a % p;
		b >>= 1;	//b右移一位
		//更新a,a依次为a^{2^0},a^{2^1},a^{2^2},....,a^{2^logb}
		a = (LL)a * a % p;
	}
	return res;
}
int main() {
	int n;
	scanf("%d", &n);
	while (n--) {
		int a, p;
		scanf("%d%d", &a, &p);
		int res = qmi(a, p - 2, p);
		//p=2时比较特殊,需要用a%p判断是否有解
		if (a % p) printf("%d\n", res);	
		//当a是p的倍数时,ab也是p的倍数,ab%p=0
		else puts("impossible");
	}
	return 0;
}
```

# 5 扩展欧几里得算法

**裴蜀定理**: 给定任意一对正整数a,b,存在非零整数x,y,使得ax+by=(a,b). 特别地, 当a,b互素时, ax+by=1.

**x与y的求解**:

由欧几里得算法拓展由欧几里得算法拓展, 设 d = gcd(a,b).

**方式一:** $exgcd(a,b,x,y)=exgcd(b,a\% b,y,x)$. $exgcd(b,a\% b,y,x)⇒b×y+(a−[\frac ab]×b)×x=d⇒b×(y−[\frac ab]×x)+a×x=d$, y更新为$y−[\frac ab]×x$.

**方式二:** $exgcd(a,b,x,y)=exgcd(b,a\% b,x,y)$. $exgcd(b,a\% b,x,y)⇒b×x+(a−[\frac ab]×b)×y=d⇒p×(x−[\frac ab]×y)+a×y$, y更新为$x−[\frac ab]×y$,x更新为$y$.

**对于求解更一般的方程 ax+by=c:**设 d=gcd(a,b) 则其有解当且仅当 d|c, 求解方法如下:

用扩展欧几里得求出 $ax_0+by_0=d$ 的解, 则$a(x_0×\frac cd)+b(y_0×\frac cd)=c$, 故而特解为 $x^′=x_0×\frac cd,y^′=y_0×\frac cd$.

通解 = 特解 + 齐次解, 而齐次解即为方程 $ax+by=0$的解.

所以通解为 $x=x^′+k×\frac bd,y=y^′−k×\frac ad\ k∈z$. 若令 $t=\frac bd$, 则对于 x 的最小非负整数解为 $(x^′\%t+t)\%t$.

算法复杂度: O(n∗log(a+m)).

### [877. 扩展欧几里得算法](https://www.acwing.com/problem/content/879/)

给定 n 对正整数 ai,bi, 对于每对数, 求出一组 xi,yi, 使其满足 $a_i×x_i+b_i×y_i=gcd(a_i,b_i)$.

```c++
int exgcd(int a, int b, int& x, int& y) {
	if (!b) {	//如果b=0,那么1a+0b=(a,b)=a
		x = 1, y = 0;	//边界情况
		return a;
	}
	int d = exgcd(b, a % b, y, x);	//此时by+(a%b)x=(a,b)=d
	y -= a / b * x;		//推到新的a, b的系数
	return d;
}
int main() {
	int n;
	scanf("%d", &n);
	while (n--) {
		int a, b, x, y;
		scanf("%d%d", &a, &b);
		exgcd(a, b, x, y);
		printf("%d %d\n", x, y);
	}
	return 0;
}
```

### [878. 线性同余方程](https://www.acwing.com/problem/content/880/)

给定 n 组数据 ai,bi,mi, 对于每组数求出一个 xi, 使其满足 $a_i×x_i≡b_i(mod\ m_i)$, 如果无解则输出 `impossible`.

**解题思路:**求解一次同余方程 ax≡b(modm), 则等价于求ax=m∗(−y)+b, 即ax+my=b

有解条件为 gcd(a,m)|b,然后用扩展欧几里得求解即可

特别的 当 b=1 且 a与m互质时 则所求的x即为a的逆元.

```c++
int exgcd(int a, int b, int& x, int& y) {
	if (!b) {	//如果b=0,那么1a+0b=(a,b)=a
		x = 1, y = 0;	//边界情况
		return a;
	}
	int d = exgcd(b, a % b, y, x);	//此时by+(a%b)x=(a,b)=d
	y -= a / b * x;		//推到新的a, b的系数
	return d;
}
int main() {
	int n;
	scanf("%d", &n);
	while (n--) {
		int a, b, m;
		scanf("%d%d%d", &a, &b, &m);
		int x, y;
		int d = exgcd(a, m, x, y);
		if (b % d) puts("impossible");
		else printf("%d\n", (LL)x * (b / d) % m);
	}
	return 0;
}
```

# 6 中国剩余定理

一般地, 设 $m_1, m_2, \cdots , m_s$ 是两两互素的大于 1 的整数, $b_1,b_2,\cdots ,b_s$是任意给定的整数, 一次同余方程组$x≡b_i(mod\ m_i),i=1,2,…,s$, 在 ZZ 中有解, 它的全部解是
$c+km_1m_2\cdots m_s,k∈\Z$,

其中, $c=b_1v_1\prod \limits_{j≠1}m_j+b_2v_2\prod \limits_{j≠2}m_j+\cdots +b_sv_s\prod \limits_{j≠m}m_j$; $v_i$ 满足 $u_im_i+v_i\prod \limits_{j≠i}m_j=1,i=1,2,\cdots ,s$.

### [204. 表达整数的奇怪方式](https://www.acwing.com/problem/content/206/)

给定 2n 个整数 a1,a2,…,an 和 m1,m2,…,mn, 求一个最小的非负整数 x, 满足 $∀i∈[1,n],x≡m_i(mod\ a_i)$.

**解题思路:**

对于每两个式子, 考虑将其合并：

$\left\{\begin{align} x≡m_1(mod\ a_1)\\x≡m_2(mod\ a_2) \end{align}\right. \ $ $⇒$ $\left\{\begin{align} x=k_1×a_1+m_1\\x=k_2×a_2+m_2 \end{align}\right.$

$k_1×a_1+m_1=k_2×a_2+m_2⇒k_1×a_1−k_2×a_2=m_2−m_1$

得出结论：① $k_1×a_1+k_2×(−a_2)=m_2−m_1$

于是乎, 我们就可以用扩展欧几里得算法找出 k^′^~1~,k^′^~2~ 满足 $k^′_1×a_1+k^′_2×(−a_2)=(a_1,−a_2)$, 无解情况就是 $(a_1,−a_2)∤m_2−m_1$. 所以我们只需要让 k^′^~1~ 和 k^′^~2~ 分别扩大 $\frac{m_2−m_1}{(a_1,−a_2)}$, 就可以找到 k~1~,k~2~满足 ① 式.

接着, 可以通过扩展欧几里得算法的通解 $\left\{\begin{align} k_1=k_1+k×\frac{a_2}{(a_1,−a_2)}\\ k_2=k_2+k×\frac{a_1}{(a_1,−a_2)} \end{align}\right. $, 求出题目要求的最小非负整数解 $\left\{\begin{align} k_1=k_1\ mod\ \frac{a_2}{(a_1,−a_2)}\\ k_2=k_2\ mod \ \frac{a_1}{(a_1,−a_2)} \end{align}\right.$. 将上式代入：

$x=(k1+k×\frac{a_2}{(a_1,−a_2)})×a_1+m_1=k_1×a_1+k×\frac{a_2×a_1}d+m_1=k_1×a_1+k×[a_1,a_2]+m_1$.我们设 $a_0=[a_1,a_2]$, $m_0=k_1×a_1+m_1$, x 就变成了 $a_0×k+m_0$, 问题回到了最开始.

**注意事项: **开 long long, 有的地方要取绝对值, 否则会模负数.

```c++
//拓展的欧几里得算法
LL exgcd(LL a, LL b, LL& x, LL& y){
    if (!b){
        x = 1, y = 0;
        return a;
    }
    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x; 
    return d;
}
int main(){
    int n;
    cin >> n;
    bool has_answer = true;
    LL a1, m1;
    cin >> a1 >> m1;    //首先输入第一个方程
    for (int i = 0; i < n - 1; i++) {    //后面的方程
        LL a2, m2;
        cin >> a2 >> m2;
        LL k1, k2;
        //用拓展的欧几里得算法求k1a1+m1=k2a2+m2的系数
        LL d = exgcd(a1, a2, k1, k2);
        //有解等价于(a1, a2)|m2-m1
        if ((m2 - m1) % d) {    //判断方程是否有解
            has_answer = false;
            break;
        }
        //把等式右边从d扩大到m2-m1
        k1 *= (m2 - m1) / d;
        //x=(k1+k*(a2/d))a1+m1
        LL t = a2 / d;
        //把k1变成最小的正整数解
        k1 = (k1 % t + t) % t;
        m1 = a1 * k1 + m1;
        a1 = abs(a1 / d * a2);
    }
    if (has_answer) {   //m1 mod a1 的正余数
        cout << (m1 % a1 + a1) % a1 << endl;
    }
    else puts("-1");
    return 0;
}
```

# 7 高斯消元

高斯消元时间复杂度: O(n3).

通过初等行变换 把**增广矩阵**化为**阶梯型矩阵**并回代得到方程的解; 适用于求解包含n个方程, n个未知数的多元线性方程组.

例如题目中的方程组增广矩阵为:

$$
\left(
\begin{aligned}
&a_{11}\quad a_{12}\quad \cdots \quad a_{1n}\quad b_1\\
&a_{21}\quad a_{22}\quad \cdots \quad a_{2n}\quad b_2\\
&\cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \\
&a_{n1}\quad a_{n2}\quad \cdots \quad a_{nn}\quad b_n\\
\end{aligned}
\right)
$$

接下来的所有操作都用该增广矩阵, 代替原方程组.

> **前置知识：初等行(列)变换**
> 
> 1. 把某一行乘一个非0的数 (方程的两边同时乘上一个非0数不改变方程的解);
> 2. 交换某两行 (交换两个方程的位置);
> 3. 把某行的若干倍加到另一行上去 (把一个方程的若干倍加到另一个方程上去).

接下来, 运用初等行变换, 把增广矩阵, 变为上三角矩阵. 最后再把阶梯型矩阵从下到上回代到第一层即可得到方程的解.

### [883. 高斯消元解线性方程组](https://www.acwing.com/problem/content/885/)

输入一个包含 n 个方程 n 个未知数的线性方程组. 方程组中的系数为实数. 求解这个方程组.

下图为一个包含 m 个方程 n 个未知数的线性方程组示例：

$$
\left\{
\begin{aligned}
&a_{11}x_1+a_{12}x_2+\cdots a_{1n}x_n=b_1\\
&a_{21}x_1+a_{22}x_2+\cdots a_{2n}x_n=b_2\\
&\cdots \\
&a_{n1}x_1+a_{n2}x_2+\cdots a_{nn}x_n=b_n\\
\end{aligned}
\right.
$$

**解题思路:**

枚举每一列c,

- 找到当前列绝对值最大的一行;
- 用初等行变换(2) 把这一行换到最上面(未确定阶梯型的行, 并不是第一行);
- 用初等行变换(1) 将该行的第一个数变成 1(其余所有的数字依次跟着变化);
- 用初等行变换(3) 将下面所有行的当且列的值变成 0;

```c++
const int N = 110;
const double eps = 1e-8;	//浮点数的判断有误差
int n;
double a[N][N];
//高斯消元, 答案存于a[i][n]中, 0 <= i < n
int gauss() {
	int c, r;	//当前枚举的列数col和行数row
	//从左往右枚举每一列,每次找到每列中最大的一行
	for (c = 0, r = 0; c < n; c++) {
		int t = r;	//对于前面的r-1行已经处理完,从第r行开始枚举
		for (int i = r; i < n; i++) //枚举下面r行中当前列的最大值
			if (fabs(a[i][c]) > fabs(a[t][c])) t = i;
		//如果这一列全部为0,不需要进行处理,继续判断下一列
		if (fabs(a[t][c]) < eps) continue;
		//把这一列系数最大的一行交换到未处理的几行的最上面
		for (int i = c; i <= n; i++) swap(a[t][i], a[r][i]);
		//把当前这一行的第一个数变成1(方程两边同时除以这个系数),最后更新第一个数
		for (int i = n; i >= c; i--) a[r][i] /= a[r][c];
		//用当前行把下面所有行的第c列消成0(如果是0就不需要操作)
		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) {	//消完之后剩余方程的个数小于n
		for (int i = r; i < n; i++)
			if (fabs(a[i][n]) > eps)
				return 2;	//出现0!=0的情况,没有解
		return 1;	//有无穷多组解
	}
	//最后倒着把方程消一遍,除首项系数为1,其他消成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;	//有唯一解
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j <= n; j++)
			cin >> a[i][j];	//输入方程组
	int t = gauss();
	if (t == 2) puts("No solution");	//无解
	else if (t == 1) puts("Infinite group solutions");	//无数组解
	else {	//有唯一解
		for (int i = 0; i < n; i++) {
			if (fabs(a[i][n]) < eps) a[i][n] = 0;  //去掉输出 -0.00 的情况
			printf("%.2lf\n", a[i][n]);
		}
	}
	return 0;
}
```

### [884. 高斯消元解异或线性方程组](https://www.acwing.com/problem/content/886/)

输入一个包含 n 个方程 n 个未知数的异或线性方程组. 方程组中的系数和常数为 0 或 1, 每个未知数的取值也为 0 或 1. 求解这个方程组.

异或线性方程组示例如下：

```
M[1][1]x[1] ^ M[1][2]x[2] ^ … ^ M[1][n]x[n] = B[1]
M[2][1]x[1] ^ M[2][2]x[2] ^ … ^ M[2][n]x[n] = B[2]
…
M[n][1]x[1] ^ M[n][2]x[2] ^ … ^ M[n][n]x[n] = B[n]
```

其中 `^` 表示异或(XOR), `M[i][j]` 表示第 i 个式子中 `x[j]` 的系数, `B[i]` 是第 i 个方程右端的常数, 取值均为 0 或 1.

**解题思路:**

高斯消元得到上三角矩阵:

枚举列, 找到当前列的非零行, 非零行换到剩余行的最上面, 剩余行中除去最上面一行, 下面所有行的当前列都消零.

判断解的种类:

无解, 无穷多解, 唯一解.

```c++
const int N = 110;
int n;
int a[N][N];
int gauss() {
	int r, c;
	for (r = c = 0; c < n; c++) {
		int t = r;
		for (int i = r; i < n; i++) {
			if (a[i][c]) {
				t = i;	//找到命中注定的人
				break;
			}
		}
		if (!a[t][c]) continue;
		//把命中注定的人换到重要的位置上去
		for (int i = c; i <= n; i++)
			swap(a[t][i], a[r][i]);
		for (int i = r + 1; i < n; i++)
			if (a[i][c])
				for (int j = c; j <= n; j++)
					a[i][j] ^= a[r][j];
		r++;
	}
	if (r < n) {
		for (int i = r; i < n; i++)
			if (a[i][n])
				return 2;
		return 1;
	}
	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;
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n + 1; j++)
			cin >> a[i][j];
	int res = gauss();
	if (res == 0) {
		for (int i = 0; i < n; i++)
			cout << a[i][n] << endl;
	}
	else if (res == 1) puts("Multiple sets of solutions");
	else puts("No solution");
	return 0;
}
```

# 8 组合计数

### [885. 求组合数 I](https://www.acwing.com/problem/content/887/)

给定 n 组询问, 每组询问给定两个整数 a, b, 请你输出 $C^b_a\ mod\ (10^9+7)$ 的值.

数据范围: 1≤n≤10000, 1≤b≤a≤2000.

**解题思路: **递推公式求组合数 O(n^2^)

递推式: $C^b_a=C^{b−1}_{a−1}+C^b_{a−1}$

$C^b_a$的含义就是可以理解成从Acwing网站中a位巨佬中选出b位巨佬的总方案数a, 位巨佬中抽出b位巨佬的方案数可以分为两类:

1. 选抽巨佬, 那么此时已经选出了一位抽风巨佬, 剩下只要从a-1位巨佬中选出b-1位巨佬.
2. 不选抽风巨佬, 那么此时情况显然就是从剩下a-1位巨佬中选出b位巨佬.

```c++
const int N = 2010, mod = 1e9 + 7;
int c[N][N];
void init() {
	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])%mod;
}
int main() {
	init();
	int n;
	scanf("%d", &n);
	while (n--) {
		int a, b;
		scanf("%d%d", &a, &b);
		printf("%d\n", c[a][b]);
	}
	return 0;
}
```

### [886. 求组合数 II](https://www.acwing.com/problem/content/888/)

给定 n 组询问, 每组询问给定两个整数 a, b, 请你输出 $C^b_a\ mod\ (10^9+7)$ 的值.

数据范围: 1≤n≤10000, 1≤b≤a≤10^5^.

**解题思路: **快速幂求组合数 O(a×log(mod))

公式: $C^b_a=\frac{a!}{b!(a-b)!}=a! \times b!^{-1} \times (a-b)!^{-1}$

b!^−1^与(a−b)!^−1^利用快速幂求逆元:

$b!^{−1}=((b−1)!b)^{−1}=(b−1)!^{−1}\times b^{−1}$;

$b^{−1}=b^{10^9+5}$(根据费马小定理);

得$b!^{−1}=(b−1)!^{−1}\times b^{10^9+5}=(b−1)!^{−1}\times b^{(mod\ −2)}$.

因为mod=1e9+7是质数,所以2~1e9+6与1e9+7互质,所以可以使用费马小定理来求解逆元,逆元通过快速幂求解.

```c++
const int N = 1e5 + 10, mod = 1e9 + 7;
int fact[N], infact[N];	//阶乘和阶乘的逆模上mod的值

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;
}
int main() {
	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;
	}
	int n;
	scanf("%d", &n);
	while (n--) {
		int a, b;
		scanf("%d%d", &a, &b);
		printf("%d\n", (LL)fact[a] * infact[b] % mod * infact[a - b] % mod);
	}
	return 0;
}
```

### [887. 求组合数 III](https://www.acwing.com/problem/content/889/)

给定 n 组询问, 每组询问给定三个整数 a,b,p, 其中 p 是质数, 请你输出 $C^b_a\ mod\ p$ 的值.

数据范围: 1≤n≤20, 1≤b≤a≤10^18^, 1≤p≤10^5^.

**解题思路: **卢卡斯定理 Lucas Theory O(log~p~N p logp)

卢卡斯定理: $C^b_a(lucas)≡C^{\lfloor b/p\rfloor}_{\lfloor a/p\rfloor }(lucas)C^{b\ mod\ p}_{a\ mod\ p}(mod\ p)$

证明用到的两个等式:

$$
(1+x)^p≡(1+x^p)\ (mod\ p)\\
(1+x)^{p^a}≡(1+x^{p^a})\ (mod\ p)
$$

**step 1: **首先我们可以把 a、b 转化为 p 进制数：

$$
a=a_k⋅p^k+a_{k−1}⋅p^{k−1}+\cdots +a_1⋅p^1+a_0⋅p^0\\
b=b_k⋅p^k+b_{k−1}⋅p^{k−1}+\cdots +b_1⋅p^1+b_0⋅p^0
$$

**step 2:** 则有：

$$
\begin{aligned}
&(1+x)^a=(1+x)^{a_k⋅p^k+a_{k−1}⋅p^{k−1}+\cdots +a_1⋅p^1+a_0⋅p^0}\\
&=(1+x)^{a_k⋅p^k}⋅(1+x)^{a_{k−1}⋅p^{k−1}}⋅\ldots ⋅(1+x)^{a_1⋅p^1}⋅(1+x)^{a_0⋅p^0}\\
&\equiv (1+x^{p^k})^{a_k}⋅(1+x^{p^{k−1}})^{a_{k−1}}⋅\ldots ⋅(1+x^{p^1})^{a_1}⋅(1+x^{p^0})^{a_0}
\end{aligned}
$$

**step 3:** 我们想求得 $C^b_a$, 其在等式左边即为 x^b^ 的系数.

在等式右边也为 x^b^ 的系数, 由 b 的 p 进制可得：$x^b=x^{b_k⋅p^k+b_{k−1}⋅p^{k−1}+…+b_1⋅p^1+b_0⋅p^0}$, 显然, $x^{b_k}⋅p^k$ 项在 $(1+x^{p^k})^{a_k}$ 中是 $C^{b_k}_{a_k}⋅x^{b_k⋅p^k}$, 同理 $x^{b_{k−1}⋅p^{k−1}}$ 项在 $(1+x^{p^{k−1}})^{a_{k−1}}$ 中是 $C^{b_{k−1}}_{a_{k−1}}⋅x^{b_{k−1}⋅p^{k−1}}$, 同理可求得 $x^b$ 的系数为：$C^{b_k}_{a_k}⋅C^{b_{k−1}}_{a_{k−1}}⋅…⋅C^{b_1}_{a_1}⋅C^{b_0}_{a_0}$ 因此可得：$C^b_a≡C^{b_k}_{a_k}⋅C^{b_{k−1}}_{a_{k−1}}⋅…⋅C^{b_1}_{a_1}⋅C^{b_0}_{a_0}\ (mod\ p)$.

**step 4:** 已经得到了答案, 只需要转化成简单的形式：

因为 a、b 是 p 进制数, 所以有 $a_0=a\ mod\ p$、$b_0=b\ mod\ p$. 我们让 a、b 在 p 进制中右移一位, 即 $⌊\frac ap⌋$、$⌊\frac bp⌋$. 对于 $⌊\frac ap⌋$、$⌊\frac bp⌋$ 重复上面最开始的步骤, 同样可以得到： $C^{\lfloor b/p\rfloor}_{\lfloor a/p\rfloor }≡C^{b_k}_{a_k}⋅C^{b_{k−1}}_{a_{k−1}}⋅…⋅C^{b_1}_{a_1}\ (mod\ p)$.

因此：$C^b_a≡C^{\lfloor b/p\rfloor}_{\lfloor a/p\rfloor }\ C^{b\ mod\ p}_{a\ mod\ p}\ (mod\ p)$

```c++
int 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;
}
int C(int a, int b) {
	int res = 1;
	for (int i = 1, j = a; i <= b; i++, j--) {
		res = (LL)res * j % p;
		res = (LL)res * qmi(i, p - 2) % p;
	}
	return res;
}
int lucas(LL a, LL b) {
	if (a < p && b < p) return C(a, b);
	//a%p后肯定是<p的,所以可以用C(),但a/p后不一定<p 所以用lucas继续递归
	return (LL)C(a % p, b % p) * lucas(a / p, b / p) % p;
}
int main() {
	int n;
	scanf("%d", &n);
	while (n--) {
		LL a, b;
		scanf("%lld%lld%d", &a, &b, &p);
		printf("%d\n", lucas(a, b));
	}
	return 0;
}
```

### [888. 求组合数 IV](https://www.acwing.com/problem/content/890/)

输入 a,b, 求 $C^b_a$ 的值. 注意结果可能很大, 需要使用高精度计算.

数据范围: 1≤b≤a≤5000.

**解题思路: **线性筛筛出来所有质数, 用代码实现求阶乘质因数, 用高精度乘法乘出来答案.

从组合公式$C^b_a=\frac{a!}{b!(a−b)!}$入手, 这次不是让我们模一个数之后再输出了, 要求我们用高精度算法, 第一个想到的高精度除法其实并不可行, 高精除不仅难写而且慢.

所以我们想到先把式子分解质因数再高精度乘法, 这里有一个求阶乘质因数的方法：a!中质因数p的个数$cnt(a,p)=⌊\frac ap⌋+⌊\frac a{p^2}⌋+⌊\frac a{p^3}⌋+⋯$.

cnt(a,p)−cnt(b,p)−cnt(a−b,p)即是$C^b_a$中p的个数, 所求答案即为$p_1^{sum_1}×p_2^{sum_2}×⋯×p_i^{sum_i}$.

```c++
const int N = 5010;
int primes[N], cnt;
int sum[N];
bool st[N];
//线性筛法求1~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;
}

int main() {
	int a, b;
	cin >> a >> b;
	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++)	//遍历sum[i]遍
			res = mul(res, primes[i]);	//求primes[i]^sum[i]
	for (int i = res.size() - 1; i >= 0; i--) printf("%d", res[i]);
	puts("");
	return 0;
}
```

### [889. 满足条件的01序列](https://www.acwing.com/problem/content/891/)

给定 n 个 0 和 n 个 1, 它们将按照某种顺序排成长度为 2n 的序列, 求它们能排列成的所有序列中, 能够满足任意前缀序列中 0 的个数都不少于 1 的个数的序列有多少个. 输出的答案对 10^9^+7 取模.

**解题思路:** 卡特兰数

卡特兰数为: $\frac{C^n_{2n}}{n+1}=\frac 1{n+1}×\frac{a×(a−1)×…×(a−b+1)}{1×2×…×b}\ (a=2n, b=n)$.

下面看一下卡特兰数的公式是如何推导出来的. 首先我们需要将上述问题转换成一个等价的问题：在一个二维平面内, 从(0, 0)出发到达(n, n), 每次可以向上或者向右走一格, 0代表向右走一个, 1代表向上走一格, 则每条路径都会代表一个01序列, 则满足任意前缀中0的个数不少于1个数序列对应的路径则右下侧.

符合要求的路径必须严格在上图中红色线的下面(不可以碰到图中的红线, 可以碰到绿线). 则我们考虑任意一条不合法路径, 例如下图：

![image-20210416105556735.png](https://www.rearwaves.com/usr/assets/algorithm/math/61813_0e754fd29e-image-20210416105556735.png)

所有路径的条数为 $C^n_{2n}$, 其中不合法的路径有 $C^{n−1}_{2n}$ 条, 因此合法路径有：

$$
\begin{aligned}
C^n_{2n}−C^{n−1}_{2n}&=\frac{(2n)!}{n!×n!}−\frac{(2n)!}{(n+1)!×(n−1)!}\\
&=\frac{(2n)!×(n+1)}{n!×(n+1)!}−\frac{(2n)!×n}{n!×(n+1)!}\\
&=\frac{(2n)!×(n+1)−(2n)!×n}{n!×(n+1)!}\\
&=\frac{(2n)!}{n!×(n+1)!}=\frac 1{n+1}×\frac{(2n)!}{n!×n!}\\
&=\frac{C^n_{2n}}{n+1}
\end{aligned}
$$

推导完毕.

> 除了上述两种问题, 如下问题对应的答案也是卡特兰数：
> 
> 1. n个结点的二叉树数量h(n); 其实有递推公式, 即：$h(n)=\sum_{i=1}^nh(i−1)×h(n−i)\quad h(0)=1$
> 2. 矩阵链乘：$P=A_1×A_2×…×A_n$, 有多少种不同的计算次序？(相当于加括号, 问合法括号序列有多少个)
> 3. 一个栈(无穷大)的进栈序列为1, 2, 3, …, n, 有多少个不同的出栈序列?
> 4. 有2n个人排成一行进入剧场. 入场费5元. 其中只有n个人有一张5元钞票, 另外n人只有10元钞票, 剧院无其它钞票, 问有多少中方法使得只要有10元的人买票, 售票处就有5元的钞票找零？(将持5元者到达视作将5元入栈, 持10元者到达视作使栈中某5元出栈)

因为mod是质数, 因此任何数与mod都互质, 可以使用快速幂求逆元, 否则需要使用扩展欧几里得算法求逆元.

```c++
const int N = 1e5 + 10, mod = 1e9 + 7;
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;
}
int main() {
	int n;
	cin >> n;
	int a = n * 2, b = n;
	int res = 1;
	for (int i = a; i > a - b; i--)
		res = (LL)res * i % mod;
	for (int i = 1; i <= b; i++)
		res = (LL)res * qmi(i, mod - 2, mod) % mod;
	res = (LL)res * qmi(n + 1, mod - 2, mod) % mod;
	cout << res << endl;
	return 0;
}
```

# 9 容斥原理

**容斥原理：**

对于$S_1, S_2, S_3,$有如下公式：

$$
S_1\cup S_2\cup S_3 = S_1+S_2+S_3 − S_1∩S_2 − S_1∩S_3 − S_2∩S_3 + S_1∩S_2∩S_3一般的,
$$

一般的,  设U中元素有n种不同的属性, 而第i种属性称为P~i~拥有属性P~i~的元素构成集合S~i~,那么:

$$
\begin{aligned}
\left|\bigcup_{i=1}^{n} S_{i}\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|-\ldots \\
& +(-1)^{m-1} \sum_{a_{i}<a_{i+1}}\left|\bigcap_{i=1}^{m} S_{a_{i}}\right|+\cdots+(-1)^{n-1}\left|S_{1} \cap \cdots \cap S_{n}\right|
\end{aligned}
$$

即: $\left|\bigcup_{i=1}^{n} S_{i}\right|=\sum_{m=1}^{n}(-1)^{m-1} \sum_{a_{i}<a_{i+1}}\left|\bigcap_{i=1}^{m} S_{a_{i}}\right|$.

$2^n−1=C^1_n−C^2_n+C^3_n…(−1)^kC^n_n$(可将它类比成每个数选或不选)
一共有2n−1个状态, 对每一种状态求出 累乘的结果t,和这种状态选择的数的个数cnt. n/t用于求出 t 的倍数1~n中会出现几次, cnt为奇数加上, cnt为偶数减去.

### [890. 能被整除的数](https://www.acwing.com/problem/content/892/)

给定一个整数 n 和 m 个不同的质数 $p_1,p_2,…,p_m$.

请你求出 1∼n 中能被 $p_1,p_2,…,p_m$ 中的至少一个数整除的整数有多少个.

**解题思路: **

样例: n = 10, p1=2,p2=3, 求1-10中能满足能整除p1或p2的个数, 即`2, 3, 4, 6, 8, 9, 10`,共7个.

记S~i~为1~n 中能整除p~i~的集合,那么根据容斥原理, 所有数的个数为各个集合的并集, 计算公式如下:

$$
\begin{aligned}
⋃\limits_{i=1}^mS_i&=S_1+S_2+…+S_m−(S_1∩S_2+S_1∩S_3+…+S_{m−1}∩S_m)\\
&+(S_1∩S_2∩S_3+…+S_{m−2}∩S_{m−1}∩S_m)+…+(−1)^{m−1}(⋂\limits_{i=1}^mS)
\end{aligned}
$$

以题目样例为例: S1={2,4,6,8,10},S2={3,6,9},S1⋂S2={6},故S1⋃S2={2,3,4,6,8,9,10}.

**实现思路: **

1. 每个集合实际上并不需要知道具体元素是什么, 只要知道这个集合的大小, 大小为$|S_i|=n/p_i|$, 比如题目中$|S_1|=10/2=5,\ |S_2|=10/3=3$.
2. 交集的大小如何确定？因为p~i~均为质数, 这些质数的乘积就是他们的最小公倍数, n除这个最小公倍数就是交集的大小, 故: $|S_1⋂S_2|=\frac n{p_1×p_2}=\frac{10}{2×3}=1$.
3. 如何用代码表示每个集合的状态？这里使用的二进制, 以m = 4为例, 所以需要4个二进制位来表示每一个集合选中与不选的状态, `1101`, 这里表示选中集合$S_1,S_2,S_4$, 故这个集合中元素的个数为 $\frac{n}{p_1×p_2×p_4}$, 因为集合个数是3个, 根据公式, 前面的系数为$(−1)^{3−1}=1$. 所以到当前这个状态时, 应该是$res+=\frac{n}{p_1×p_2×p_4}$ . 这样就可以表示的范围从`0000`到`1111`的每一个状态.

```c++
const int N = 20;
int n, m;
int p[N];

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) cin >> p[i];
	int res = 0;
	for (int i = 1; i < 1 << m; i++) {	//枚举每一种选法
		//当前所有质数的乘积,当前选法中有多少个集合
		int t = 1, cnt = 0;
		for (int j = 0; j < m; j++) {	//枚举m位
			if (i >> j & 1) {	//当前这一位是1
				cnt++;
				if ((LL)t * p[j] > n) {
					t = -1;
					break;
				}
				t *= p[j];
			}
		}
		if (t != -1) {
			if (cnt % 2) res += n / t;
			else res -= n / t;
		}
	}
	cout << res << endl;
	return 0;
}
```

# 10 简单博弈论

## 10.1 Nim游戏

必胜状态, 先手进行某一个操作, 留给后手是一个必败状态时, 对于先手来说是一个必胜状态. 即先手可以走到某一个必败状态.

必败状态, 先手无论如何操作, 留给后手都是一个必胜状态时, 对于先手来说是一个必败状态. 即先手走不到任何一个必败状态.

### [891. Nim游戏](https://www.acwing.com/problem/content/893/)

给定 n 堆石子, 两位玩家轮流操作, 每次操作可以从任意一堆石子中拿走任意数量的石子(可以拿完, 但不能不拿), 最后无法进行操作的人视为失败.

问如果两人都采用最优策略, 先手是否必胜.

**解题思路: **

假设 n 堆石子, 石子数目分别是 $a_{1}, a_{2}, \ldots, a_{n}$, 如果 $a_{1} \oplus a_{2} \oplus \ldots \oplus a_{n} \neq 0$, 先手必胜; 否则先手必败.

**证明:**

- 操作到最后时, 每堆石子数都是 0, $0 \oplus 0 \oplus \ldots 0=0$.
- 在操作过程中, 如果 $a_{1} \oplus a_{2} \oplus \ldots \oplus a_{n}=x \neq 0$. 那么玩家必然可以通过拿走某一堆若干个石子将异或结果变为 0 .
  证明: 不妨设x的二进制表示中最高一位1在第k位, 那么在 $a_{1}, a_{2}, \ldots, a_{n}$ 中, 必然有一个数 $a_{i}$  , 它的第k位为时 1 , $且 a_{i} \oplus x<a_{i}$, 那么从第 i 堆石子中拿走$ \left(a_{i}-a_{i} \oplus x\right)$ 个石子, 第 i 堆石子还剩 $a_{i}-\left(a_{i}-a_{i} \oplus x\right)=a_{i} \oplus x$, 此时 $a_{1} \oplus a_{2} \oplus \ldots \oplus a_{i} \oplus x \oplus \ldots \oplus a_{n}=x \oplus x=0$.
- 在操作过程中, 如果 $a_{1} \oplus a_{2} \oplus \ldots \oplus a_{n}=0$, 那么无论玩家怎么拿, 必然会导致最终异或结果不为 0 .
- 反证法: 假设玩家从第 i 堆石子拿走若干个, 结果仍是 0 . 不妨设还剩下 $a^{\prime}$ 个, 因为不能不拿, 所以 $0 \leq a^{\prime}<a_{i}$ , 且 $a_{1} \oplus a_{2} \oplus \ldots \oplus a^{\prime} \oplus \ldots \oplus a_{n}=0$. 那么$\left(a_{1} \oplus a_{2} \oplus \ldots \oplus a_{i} \oplus \ldots a_{n}\right) \oplus\left(a_{1} \oplus a_{2} \oplus \ldots \oplus a^{\prime} \oplus \ldots \oplus a_{n}\right)=a_{i} \oplus a^{\prime}=0$, 则 $a_{i}=a^{\prime}$ , 与假设 $0 \leq a^{\prime}<a_{i}$ 矛盾.
  
  **基于上述三个证明:**

1. 如果先手面对的局面是 $a_{1} \oplus a_{2} \oplus \ldots \oplus a_{n} \neq 0$, 那么先手总可以通过拿走某一堆若干个石子, 将局面变成 $a_{1} \oplus a_{2} \oplus \ldots \oplus a_{n}=0$. 如此重复, 最后一定是后手面临最终没有石子可拿的状态. 先手必胜.
2. 如果先手面对的局面是 $a_{1} \oplus a_{2} \oplus \ldots \oplus a_{n}=0$, 那么无论先手怎么拿, 都会将局面变成 $a_{1} \oplus a_{2} \oplus \ldots \oplus a_{n} \neq 0$, 那么后手总可以通过拿走某一堆若干个石子, 将局面变成 $a_{1} \oplus a_{2} \oplus \ldots \oplus a_{n}=0$. 如此重复, 最后一定是先手面临最终没有石子可拿的状态. 先手必败.

```c++
int main() {
	int n, res = 0;
	scanf("%d", &n);
	while (n--) {
		int x;
		scanf("%d", &x);
		res ^= x;
	}
	if (res) puts("Yes");
	else puts("No");
	return 0;
}
```

### [892. 台阶-Nim游戏](https://www.acwing.com/problem/content/894/)

现在, 有一个 n 级台阶的楼梯, 每级台阶上都有若干个石子, 其中第 i 级台阶上有 a~i~ 个石子(i≥1). 两位玩家轮流操作, 每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中(不能不拿). 已经拿到地面上的石子不能再拿, 最后无法进行操作的人视为失败.

问如果两人都采用最优策略, 先手是否必胜.

**解题思路:**

在该 Nim 游戏中, 各堆石子对应的有向图游戏不是相互独立的, 不能直接使用简单 Nim 游戏的 SG 函数模型, 即根据 $S G\left(x_{i}\right)=x_{i}$ , 判断 $x_{1}{ }^{\wedge} x_{2}{ }^{\wedge} \ldots . .{ }^{\wedge} x_{n} $.

依据分析问题的常规思路, 可以尝试将非常规问题化归为已知类型的常规问题, 即尝试将有向图游戏相互关联的情况, 转化为相互独立的情况, 再利用 SG 函数模型加以解决.

从该思路出发, 尝试分析：可能存在一些无关的项, 使得其变化不影响整体判断, 进而将相互关联的有向图游戏分离为若干相互独立的 有向图游戏, 分离前后不影响整体问题的结果.

**最示始的情形:**

n=1 , 台阶数为 1 , 显然, 和简单 Nim 游戏相同, 当 $x{0} \neq 0$ 时, 先手必胜. 必胜策略：一次性全部拿走.

对于更复杂的情形, 最底层台阶一定和问题的解直接相关(游戏结束前, 必然为 $2 \rightarrow n$ 级台阶上的石子全空, 仅台阶1还剩余石子的情况).

**初止扩展:**

尝试分析 n=2 的情形:

$x_{1}=0$ : 先手只能从第二级台阶中拿, 不论先手从第二级台阶拿多少, 后手均可以将拿到第一级台阶的石子全部放到 地上, 最终, 第二级为空, 先手无法继续操作, 故先手必败.

$x_{1} \neq 0$ : 先手可以将第一级台阶的石子全部放在地上, 此时后手只能从第二级台阶上拿; 不论后手从第二级台阶拿多.

**假设:**

(可以先扩展到 n=3 或 n=4 的情形继续观察, 更容易得出该假设结论)

偶数级台阶的具体情况可能不影响整个有向图游戏的结果. 即：整个有向图游戏的结果, 只由奇数级台阶的有向图游戏决定, 且这些有向图游戏相互独立 (也即: $S G\left(x_{1}\right)^{\wedge} S G\left(x_{3}\right)^{\wedge} \ldots . .{ }^{\wedge} S G\left(x_{2 k+1}\right)=x ,  k \in N^{*}$ , 其中 $S G\left(x_{p}\right)=x_{p}$ , 若 $x \neq 0$ , 则先手必胜, 否则先手必败).

**证明:**

对于 $S G\left(x_{1}\right)^{\wedge} S G\left(x_{3}\right)^{\wedge} \ldots . .^{\wedge} S G\left(x_{2 k+1}\right)=x, k \in N^{*} $,
显然, 终止状态异或和为 0. $x \neq 0$ , 则先手必胜: 与 Nim 游戏类似:

对于先手: 取 x 的最高二进制位 k , 则必然存在某一奇数级台阶上的石子数 $4$ , 使得其第 k 个二进 制位上为 1 , 在 t 级台阶上取下 $x_{t}-\left(x_{t} \wedge x\right)$ 个数, 使得 $x_{t} \rightarrow\left(x_{t} \wedge x\right)$ , 从而使得下一个状态的异或和为 0.

对于后手:

- 若其在某一奇数级台阶上取任意个石子, 奇数级台阶对应的异或和必不为 0 (简单 Nim 游戏中 得到的结论);
- 若其在某一偶数级台阶上取任意个石子, 则先手只需要在对应的奇数级台阶上取增加的石子数到下一个偶数级台阶, 则奇数级台阶对应的异或和不变.

由此推知, 初始状态下:

- 各奇数级台阶的石子数异或和为 0 , 则先手必败;
- 各奇数级台阶的石子数异或和不为 0 , 则先手必胜.

```c++
int main() {
	int n;
	int res = 0;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int x;
		scanf("%d", &x);
		if (i % 2) res ^= x;
	}
	if (res) puts("Yes");
	else puts("No");
	return 0;
}
```

## 10.2 SG函数

**Mex运算:** 设S表示一个非负整数集合. 定义mex(S)为求不出属于集合S的最小非负整数的运算, 即：$mex(S)=min(x)$, x属于自然数, 且x不属于S.

**SG函数: **在有向图游戏中, 对于每个节点x,设从x除法共有k条有向边, 分别到达结点$y_1,y_2,…,y_k$, 定义SG(x)为x的后继结点$y_1,y_2,…,y_k$的SG(函数值构成的集合再执行mex(S)运算的结果, 即 $SG(x)=mex(SG(y1),SG(y2),…,SG(yn))$.

特别的, 整个有向图游戏G的SG函数值被定义为有向图游戏起点s的SG函数值, 即：$SG(G)=SG(s)$.

**有向图游戏的和: **设$G_1,G_2,…,G_m$是m个有向图游戏. 定义有向图游戏G, 它的行动规则是任选某个有向图游戏$G_i$, 并在$G_i$上行动一步. G被称为有向图游戏$G_1,G_2,…,G_m$的和.

有向图游戏的和SG函数在数值上等于它所包含的各个子游戏SG函数的异或和, 即：$SG(G)=SG(G1)⨁SG(G2)⨁…⨁SG(Gm)$.

### [893. 集合-Nim游戏](https://www.acwing.com/problem/content/895/)

给定 n 堆石子以及一个由 k 个不同正整数构成的数字集合 S. 现在有两位玩家轮流操作, 每次操作可以从任意一堆石子中拿取石子, 每次拿取的石子数量必须包含于集合 S, 最后无法进行操作的人视为失败.

问如果两人都采用最优策略, 先手是否必胜.

**解题思路：**

对于n个图, 如果$SG(G1)⨁SG(G2)⨁…⨁SG(GN)≠0$, 则先手必胜, 否则先手必败.

h[i]表示的是每一堆石子有多少个, 将每一个h[i]看做一张有向图. 例如S=[2,5],h[1]=10. 看h[1]这张有向图：

![nimyx2.png](https://www.rearwaves.com/usr/assets/algorithm/math/49357_f3eded9d39-nimyx2.png)

**定理 1 ：**如果一个有向图游戏 G 的 SG 函数值为 0 那么先手必败, 否则先手必胜.

证明: 若一个点的 SG 函数值不为 0 那么这一个点一定能走到一个 SG 函数值为 0 的点, 因为没有后继节点的点是必败节点, 所以 SG 函数值为 0 的点就是必败节点, 故如果一个函数值为 0 的点位必败节点, 否则位为必胜节点.

**定理 2 ：**如果有 n 个游戏同时进行, 那么若 $SG(G1)\ xor\ SG(G2)\ xor … xor\ SG(Gn)==0$, 那么先手必败, 否则先手必胜.

证明: (类似于 Nim 游戏的证明)如果 `xor==0` 那么无论怎么拿, 拿完后 xor 总不等于 0, 所以若 `xor==0` 那么总会把必胜节点留给对手, 所以先手必败.

如果 $xor=x≠0$ 假设 x 的二进制表示最高位 1 是在第 k 位, 那么总能找到一个 $x_i$ 使得 $x_i$ 的二进制表示的最高位是 1 , 即 $x_i\ xor\ x<x_i$. 所以 $SG(G1)\ xor\ SG(G2)\ xor … xor\ SG(Gi)\ xor … xor\ SG(Gn)\ xor\ x=x\ xor\ x=0$, 因为总能将异或值为 0 的点留给对手, 所以先手必胜.

```c++
const int N = 110, M = 10010;
int n, m;
int s[N], f[M];
//求x个石子的这一堆sg值是多少
int sg(int x) {
	if (f[x] != -1) return f[x];	//相同石子数的石子堆,sg值相同,计算一次即可
	//因为这题中较大堆的拆分情况独立于较小堆, 这里的S必须开成局部变量
	unordered_set<int> S;	//用一个哈希表来存每一个局面能到的所有情况, 便于求mex
	for (int i = 0; i < m; i++) {
		int sum = s[i];		//这次取了几个石子
		if (x >= sum) S.insert(sg(x - sum));	//如果可以减去s[i], 则添加到S中
	}
	for (int i = 0; ; i++)	//求mex(), 即取集合中不存在的最小自然数
		if (!S.count(i))
			return f[x] = i;
}
int main() {
	cin >> m;
	for (int i = 0; i < m; i++) cin >> s[i];
	cin >> n;
	memset(f, -1, sizeof f);
	int res = 0;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		res ^= sg(x);
	}
	if (res) puts("Yes");
	else puts("No");
	return 0;
}
```

### [894. 拆分-Nim游戏](https://www.acwing.com/problem/content/896/)

给定 n 堆石子, 两位玩家轮流操作, 每次操作可以取走其中的一堆石子, 然后放入两堆**规模更小**的石子(新堆规模可以为 0, 且两个新堆的石子总数可以大于取走的那堆石子数), 最后无法进行操作的人视为失败.

问如果两人都采用最优策略, 先手是否必胜.

**解题思路:**

相比于集合-Nim, 这里的**每一堆可以变成小于原来那堆的任意大小的两堆**, 即a[i]可以拆分成(b[i],b[j]), 为了避免重复规定`b[i]>=b[j]`, 即：`a[i]>b[i]>=b[j]`. 相当于一个局面拆分成了两个局面, 由SG函数理论, 多个独立局面的SG值, 等于这些局面SG值的异或和. 因此需要存储的状态就是 `sg(b[i])^sg(b[j])`(与集合-Nim的唯一区别)

注意：因为这题中原堆拆分成的两个较小堆小于原堆即可, 因此任意一个较小堆的拆分情况会被完全包含在较大堆中, 因此 S 可以开全局.

```c++
const int N = 110;
int f[N];	//记忆化搜索
int sg(int x) {
	if (f[x] != -1) return f[x];
	unordered_set<int> S;	//存储每个局面可以到的局面
	for (int i = 0; i < x; i++)
		for (int j = 0; j <= i; j++)
			S.insert(sg(i) ^ sg(j));
	//mex操作,找到集合中不存在的最小自然数
	for (int i = 0; ; i++)
		if (!S.count(i))
			return f[x] = i;
}
int main() {
	int n;
	cin >> n;
	memset(f, -1, sizeof f);
	int res = 0;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		res ^= sg(x);
	}
	if (res) puts("Yes");
	else puts("No");
	return 0;
}
```

最后修改：2023 年 04 月 23 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

贪心讲解
评论数： 6
搜索初步
评论数： 5
图论初步
评论数： 4
欢迎使用 Typecho
评论数： 2
比赛常用技巧及库函数
评论数： 2

dvlafvodtu
看的我热血沸腾啊www.jiwenlaw.com
usukxmmttv
不错不错，我喜欢看 www.jiwenlaw.com
dcyfmsthoa
想想你的文章写的特别好www.jiwenlaw.com
jbbnknwfgc
想想你的文章写的特别好https://www.ea55.com/
igbbiexfym
想想你的文章写的特别好https://www.ea55.com/

动态规划基础
评论数： 0
考研励志
评论数： 2
搜索初步
评论数： 5
比赛常用技巧及库函数
评论数： 2
图论初步
评论数： 4

基础数学知识

RearWaves • 2023 年 04 月 23 日

# 数学知识1

# 1 质数

## 1.1 试除法

### [866. 试除法判定质数](https://www.acwing.com/problem/content/868/)

给定 n 个正整数 ai, 判定每个数是否是质数.

sqrt(n)这个函数执行的时候比较慢.

算法复杂度O(sqrt(n)).

### [867. 分解质因数](https://www.acwing.com/problem/content/869/)

用到的原理:唯一分解定理(算数基本定理))

当枚举到某一个数i的时候,n的因子里面已经不包含2-i-1里面的数,如果n%i==0,则i的因子里面也已经不包含2-i-1里面的数,因此每次枚举的数都是质数.

算法复杂度O(sqrt(n)).最好log(n).

## 1.2 筛质数

做法:把2~(n-1)中的所有的数的倍数都标记上,最后没有被标记的数就是质数.

### [868. 筛质数](https://www.acwing.com/problem/content/870/)

给定一个正整数 n, 请你求出 1∼n 中质数的个数.

**埃氏筛法(稍加优化版的筛法)**

质数定理:1~n中有n/ln n个质数.

原理:在朴素筛法的过程中只用质数项去筛.

时间复杂度:粗略估计:O(n).实际:O(nlog(logn)).1~n中,只计算质数项的话,"$\frac12+\frac13+\frac14+\frac15+…+\frac1n$"的大小约为log(logn).

**线性筛法**

若n在10的6次方的话,线性筛和埃氏筛的时间效率差不多,若n在10的7次方的话,线性筛会比埃氏筛快了大概一倍.

核心:1~n内的合数p只会被其最小质因子筛掉.

关于for循环的解释:我们枚举的时候是从小到大枚举的所有质数

# 2 约数

## 2.1 约数的性质

### [869. 试除法求约数](https://www.acwing.com/problem/content/871/)

给定 n 个正整数 ai, 对于每个整数 ai, 请你按照从小到大的顺序输出它的所有约数.

$\beta_1$ 一共有 $0\sim\alpha_1$ 种选法,$\beta_2$ 一共有 $0\sim\alpha_2$ 种选法,$\dots$,$\beta_k$ 一共有 $0\sim\alpha_k$ 种选法.

由乘法原理, 一共有 ans 个约数.int 范围内约数最多的数的个数为 15361536, 那个数为 1745944200.

约数之和为:$(p_1^0 + p_1^1 + p_2^2 +…+ p_1^{\alpha_1})(p_2^0 + p_2^1 + p_2^2 +…+ p_2^{\alpha_2})…(p_k^0 + p_k^1 + p_k^2 +…+ p_k^{\alpha_k})$

### [870. 约数个数](https://www.acwing.com/problem/content/872/)

给定 n 个正整数 ai, 请你输出这些数的乘积的约数个数, 答案对 10^9+7 取模.

$N=\prod_{i=1}^{k} p_{i}^{a_{i}}=p_{1}^{a_{1}} \cdot p_{2}^{a_{2}} \ldots p_{k}^{a_{k}}$

约数个数:  $\prod_{i=1}^{k}\left(a_{i}+1\right)=\left(a_{1}+1\right)\left(a_{2}+1\right) \ldots\left(a_{k}+1\right)$

### [871. 约数之和](https://www.acwing.com/problem/content/description/873/)

给定 n 个正整数 ai, 请你输出这些数的乘积的约数个数, 答案对 10^9+7 取模.

$N=\prod_{i=1}^{k} p_{i}^{a_{i}}=p_{1}^{a_{1}} \cdot p_{2}^{a_{2}} \ldots p_{k}^{a_{k}}$

约数之和:

```c++
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;
}
```

## 2.2 最大公约数

在库algorithm中提供了求最大公约数的方法, 具体使用方法是__gcd(a, b) 即返回了ab的最大公约数.

```c++
int main() {
    int t;
    cin >> t;
    while(t--) {
        int a, b;
        cin >> a >> b;
        cout << __gcd(a, b);
    }
}
```

**辗转相除法**

求两个正整数 a 和 b 的 最大公约数 d 则有 gcd(a,b) = gcd(b,a%b).

### [872. 最大公约数](https://www.acwing.com/problem/content/874/)

给定 n 对正整数 ai,bi, 请你求出每对数的最大公约数.

```c++
int gcd(int a, int b) {
	return b ? gcd(b, a % b) : a;
}
int main() {
	int n;
	cin >> n;
	while (n--) {
		int a, b;
		scanf("%d%d", &a, &b);
		printf("%d\n", gcd(a, b));
	}
	return 0;
}
```

# 3 欧拉函数

**欧拉函数的定义:**

**求解方法一:**

首先,  欧拉函数是一个积性函数, 当m,n互质时, $φ(mn)=φ(m)∗φ(n)$.

根据唯一分解定理知 $n=p^{a_1}_1 \times p^{a_2}_2 \times \cdots p^{a_x}_x$, 因此 $φ(n)=φ(p^{a_1}_1)\times \cdots \times φ(p^{a_x}_x)$.

对于任意一项: $φ(p^{a_s}_s)=p^{a_s}_s−p^{(a_s−1)}_s$, 从定义出发 $φ(p^{a_s}_s)$等于小于或等于$p^{a_s}_s$的正整数中与$p^{a_s}_s$互质的数的数目.

因此

**求解方法二:**

容斥原理: 设n=p_1^{α_1}×p_2^{α_2}×…×pkαk

以此类推, 公式$φ(n)=n×(1−\frac1{p_1})×(1−\frac1{p_2})×\cdots ×(1−\frac1{p_k})$展开后可得以上算式.

算法时间复杂度: $O(n\times \sqrt{a})$

### [873. 欧拉函数](https://www.acwing.com/problem/content/875/)

给定 n 个正整数 ai, 请你求出每个数的欧拉函数.

### [874. 筛法求欧拉函数](https://www.acwing.com/problem/content/876/)

给定一个正整数 n, 求 1∼n 中每个数的欧拉函数之和.

**解题思路:**

先写出线性筛算法的模板. 考虑特殊情况：若该数是质数p的话, 那么该数的欧拉函数就是p−1.

需要注意的是: 每个数的欧拉函数与质因子的次数无关. 例如：$N=2^{100}×3^{100}$, 但是N的欧拉函数还是$N×(1−\frac12)×(1−\frac13)$.

时间复杂度: O(n).

```c++
const int N = 1e6 + 10;
//筛选质数 primes[]存放已经找到的质数, cnt记录已经找到的质数数量
int primes[N], cnt; 
int phi[N];
bool st[N];		//标记某个数是不是质数

**应用: 欧拉定理：设  m  是大于1的正整数, 如果整数 a 与 m 互素, 那么$a^{φ(m)}≡1(mod m)$.**

所以$a^{φ(m)}≡1(mod\ m)$.

**费马定理: $a^{p-1}≡1(mod\ p)$.**

# 4 快速幂

预处理出$a^{2^0},a^{2^1},a^{2^2},\cdots ,a^{2^{log\ b}}$这b个数.

二进制可以表示所有数,且用单一用二进制表示时,b单一表示最大可表示为二进制形式的$2^{log\ b}$.

### [875. 快速幂](https://www.acwing.com/problem/content/877/)

给定 n 组 ai,bi,pi, 对于每组数据, 求出 $a^{b_i}_i\ mod\ p_i$ 的值.

### [876. 快速幂求逆元](https://www.acwing.com/problem/content/878/)

给定 n 组 ai,pi, 其中 pi 是质数, 求 ai 模 pi 的乘法逆元, 若逆元不存在则输出 `impossible`.

**注意**：请返回在 0∼p−1 之间的逆元.

### 乘法逆元的定义

**当m为质数时**, 求解过程如下:

由费马小定理可知: bm−1≡1modm, 而a/b≡a∗xmodm. 得: a/b∗bm−1≡a∗xmodm. 即为a∗bm−2≡a∗xmodm.

而b|a,且b与m互质,因此对于b来说,一定存在一个a也与m互质,故而a可以在两边同时约去. 因此x≡bm−2modm.

无解条件 即 b与m不互质时无解,而m为质数,所以b只能为m的倍数, 此时无解,也就是b%m==0.

**当m不是质数时**, 则需要用扩展欧几里得求逆元.

```c++
int qmi(int a, int b, int p) {
	int res = 1;
	while (b) {	//对b进行二进制化,从低位到高位
		//如果b的二进制表示的第0位为1,则乘上当前的a
		if (b & 1) res = (LL)res * a % p;
		b >>= 1;	//b右移一位
		//更新a,a依次为a^{2^0},a^{2^1},a^{2^2},....,a^{2^logb}
		a = (LL)a * a % p;
	}
	return res;
}
int main() {
	int n;
	scanf("%d", &n);
	while (n--) {
		int a, p;
		scanf("%d%d", &a, &p);
		int res = qmi(a, p - 2, p);
		//p=2时比较特殊,需要用a%p判断是否有解
		if (a % p) printf("%d\n", res);	
		//当a是p的倍数时,ab也是p的倍数,ab%p=0
		else puts("impossible");
	}
	return 0;
}
```

# 5 扩展欧几里得算法

**裴蜀定理**: 给定任意一对正整数a,b,存在非零整数x,y,使得ax+by=(a,b). 特别地, 当a,b互素时, ax+by=1.

**x与y的求解**:

由欧几里得算法拓展由欧几里得算法拓展, 设 d = gcd(a,b).

**方式一:** $exgcd(a,b,x,y)=exgcd(b,a\% b,y,x)$. $exgcd(b,a\% b,y,x)⇒b×y+(a−[\frac ab]×b)×x=d⇒b×(y−[\frac ab]×x)+a×x=d$, y更新为$y−[\frac ab]×x$.

**方式二:** $exgcd(a,b,x,y)=exgcd(b,a\% b,x,y)$. $exgcd(b,a\% b,x,y)⇒b×x+(a−[\frac ab]×b)×y=d⇒p×(x−[\frac ab]×y)+a×y$, y更新为$x−[\frac ab]×y$,x更新为$y$.

**对于求解更一般的方程 ax+by=c:**设 d=gcd(a,b) 则其有解当且仅当 d|c, 求解方法如下:

用扩展欧几里得求出 $ax_0+by_0=d$ 的解, 则$a(x_0×\frac cd)+b(y_0×\frac cd)=c$, 故而特解为 $x^′=x_0×\frac cd,y^′=y_0×\frac cd$.

通解 = 特解 + 齐次解, 而齐次解即为方程 $ax+by=0$的解.

所以通解为 $x=x^′+k×\frac bd,y=y^′−k×\frac ad\ k∈z$. 若令 $t=\frac bd$, 则对于 x 的最小非负整数解为 $(x^′\%t+t)\%t$.

算法复杂度: O(n∗log(a+m)).

### [877. 扩展欧几里得算法](https://www.acwing.com/problem/content/879/)

给定 n 对正整数 ai,bi, 对于每对数, 求出一组 xi,yi, 使其满足 $a_i×x_i+b_i×y_i=gcd(a_i,b_i)$.

### [878. 线性同余方程](https://www.acwing.com/problem/content/880/)

给定 n 组数据 ai,bi,mi, 对于每组数求出一个 xi, 使其满足 $a_i×x_i≡b_i(mod\ m_i)$, 如果无解则输出 `impossible`.

**解题思路:**求解一次同余方程 ax≡b(modm), 则等价于求ax=m∗(−y)+b, 即ax+my=b

有解条件为 gcd(a,m)|b,然后用扩展欧几里得求解即可

特别的 当 b=1 且 a与m互质时 则所求的x即为a的逆元.

```c++
int exgcd(int a, int b, int& x, int& y) {
	if (!b) {	//如果b=0,那么1a+0b=(a,b)=a
		x = 1, y = 0;	//边界情况
		return a;
	}
	int d = exgcd(b, a % b, y, x);	//此时by+(a%b)x=(a,b)=d
	y -= a / b * x;		//推到新的a, b的系数
	return d;
}
int main() {
	int n;
	scanf("%d", &n);
	while (n--) {
		int a, b, m;
		scanf("%d%d%d", &a, &b, &m);
		int x, y;
		int d = exgcd(a, m, x, y);
		if (b % d) puts("impossible");
		else printf("%d\n", (LL)x * (b / d) % m);
	}
	return 0;
}
```

# 6 中国剩余定理

其中, $c=b_1v_1\prod \limits_{j≠1}m_j+b_2v_2\prod \limits_{j≠2}m_j+\cdots +b_sv_s\prod \limits_{j≠m}m_j$; $v_i$ 满足 $u_im_i+v_i\prod \limits_{j≠i}m_j=1,i=1,2,\cdots ,s$.

### [204. 表达整数的奇怪方式](https://www.acwing.com/problem/content/206/)

给定 2n 个整数 a1,a2,…,an 和 m1,m2,…,mn, 求一个最小的非负整数 x, 满足 $∀i∈[1,n],x≡m_i(mod\ a_i)$.

**解题思路:**

对于每两个式子, 考虑将其合并：

$\left\{\begin{align} x≡m_1(mod\ a_1)\\x≡m_2(mod\ a_2) \end{align}\right. \ $ $⇒$ $\left\{\begin{align} x=k_1×a_1+m_1\\x=k_2×a_2+m_2 \end{align}\right.$

$k_1×a_1+m_1=k_2×a_2+m_2⇒k_1×a_1−k_2×a_2=m_2−m_1$

得出结论：① $k_1×a_1+k_2×(−a_2)=m_2−m_1$

**注意事项: **开 long long, 有的地方要取绝对值, 否则会模负数.

# 7 高斯消元

高斯消元时间复杂度: O(n3).

通过初等行变换 把**增广矩阵**化为**阶梯型矩阵**并回代得到方程的解; 适用于求解包含n个方程, n个未知数的多元线性方程组.

例如题目中的方程组增广矩阵为:

接下来的所有操作都用该增广矩阵, 代替原方程组.

接下来, 运用初等行变换, 把增广矩阵, 变为上三角矩阵. 最后再把阶梯型矩阵从下到上回代到第一层即可得到方程的解.

### [883. 高斯消元解线性方程组](https://www.acwing.com/problem/content/885/)

输入一个包含 n 个方程 n 个未知数的线性方程组. 方程组中的系数为实数. 求解这个方程组.

下图为一个包含 m 个方程 n 个未知数的线性方程组示例：

$$
\left\{
\begin{aligned}
&a_{11}x_1+a_{12}x_2+\cdots a_{1n}x_n=b_1\\
&a_{21}x_1+a_{22}x_2+\cdots a_{2n}x_n=b_2\\
&\cdots \\
&a_{n1}x_1+a_{n2}x_2+\cdots a_{nn}x_n=b_n\\
\end{aligned}
\right.
$$

**解题思路:**

枚举每一列c,

### [884. 高斯消元解异或线性方程组](https://www.acwing.com/problem/content/886/)

输入一个包含 n 个方程 n 个未知数的异或线性方程组. 方程组中的系数和常数为 0 或 1, 每个未知数的取值也为 0 或 1. 求解这个方程组.

异或线性方程组示例如下：

```
M[1][1]x[1] ^ M[1][2]x[2] ^ … ^ M[1][n]x[n] = B[1]
M[2][1]x[1] ^ M[2][2]x[2] ^ … ^ M[2][n]x[n] = B[2]
…
M[n][1]x[1] ^ M[n][2]x[2] ^ … ^ M[n][n]x[n] = B[n]
```

其中 `^` 表示异或(XOR), `M[i][j]` 表示第 i 个式子中 `x[j]` 的系数, `B[i]` 是第 i 个方程右端的常数, 取值均为 0 或 1.

**解题思路:**

高斯消元得到上三角矩阵:

枚举列, 找到当前列的非零行, 非零行换到剩余行的最上面, 剩余行中除去最上面一行, 下面所有行的当前列都消零.

判断解的种类:

无解, 无穷多解, 唯一解.

# 8 组合计数

### [885. 求组合数 I](https://www.acwing.com/problem/content/887/)

给定 n 组询问, 每组询问给定两个整数 a, b, 请你输出 $C^b_a\ mod\ (10^9+7)$ 的值.

数据范围: 1≤n≤10000, 1≤b≤a≤2000.

**解题思路: **递推公式求组合数 O(n^2^)

递推式: $C^b_a=C^{b−1}_{a−1}+C^b_{a−1}$

$C^b_a$的含义就是可以理解成从Acwing网站中a位巨佬中选出b位巨佬的总方案数a, 位巨佬中抽出b位巨佬的方案数可以分为两类:

### [886. 求组合数 II](https://www.acwing.com/problem/content/888/)

给定 n 组询问, 每组询问给定两个整数 a, b, 请你输出 $C^b_a\ mod\ (10^9+7)$ 的值.

数据范围: 1≤n≤10000, 1≤b≤a≤10^5^.

**解题思路: **快速幂求组合数 O(a×log(mod))

公式: $C^b_a=\frac{a!}{b!(a-b)!}=a! \times b!^{-1} \times (a-b)!^{-1}$

b!^−1^与(a−b)!^−1^利用快速幂求逆元:

$b!^{−1}=((b−1)!b)^{−1}=(b−1)!^{−1}\times b^{−1}$;

$b^{−1}=b^{10^9+5}$(根据费马小定理);

得$b!^{−1}=(b−1)!^{−1}\times b^{10^9+5}=(b−1)!^{−1}\times b^{(mod\ −2)}$.

因为mod=1e9+7是质数,所以2~1e9+6与1e9+7互质,所以可以使用费马小定理来求解逆元,逆元通过快速幂求解.

```c++
const int N = 1e5 + 10, mod = 1e9 + 7;
int fact[N], infact[N];	//阶乘和阶乘的逆模上mod的值

### [887. 求组合数 III](https://www.acwing.com/problem/content/889/)

给定 n 组询问, 每组询问给定三个整数 a,b,p, 其中 p 是质数, 请你输出 $C^b_a\ mod\ p$ 的值.

数据范围: 1≤n≤20, 1≤b≤a≤10^18^, 1≤p≤10^5^.

**解题思路: **卢卡斯定理 Lucas Theory O(log~p~N p logp)

卢卡斯定理: $C^b_a(lucas)≡C^{\lfloor b/p\rfloor}_{\lfloor a/p\rfloor }(lucas)C^{b\ mod\ p}_{a\ mod\ p}(mod\ p)$

证明用到的两个等式:

$$
(1+x)^p≡(1+x^p)\ (mod\ p)\\
(1+x)^{p^a}≡(1+x^{p^a})\ (mod\ p)
$$

**step 1: **首先我们可以把 a、b 转化为 p 进制数：

$$
a=a_k⋅p^k+a_{k−1}⋅p^{k−1}+\cdots +a_1⋅p^1+a_0⋅p^0\\
b=b_k⋅p^k+b_{k−1}⋅p^{k−1}+\cdots +b_1⋅p^1+b_0⋅p^0
$$

**step 2:** 则有：

**step 3:** 我们想求得 $C^b_a$, 其在等式左边即为 x^b^ 的系数.

**step 4:** 已经得到了答案, 只需要转化成简单的形式：

因此：$C^b_a≡C^{\lfloor b/p\rfloor}_{\lfloor a/p\rfloor }\ C^{b\ mod\ p}_{a\ mod\ p}\ (mod\ p)$

```c++
int p;

### [888. 求组合数 IV](https://www.acwing.com/problem/content/890/)

输入 a,b, 求 $C^b_a$ 的值. 注意结果可能很大, 需要使用高精度计算.

数据范围: 1≤b≤a≤5000.

**解题思路: **线性筛筛出来所有质数, 用代码实现求阶乘质因数, 用高精度乘法乘出来答案.

cnt(a,p)−cnt(b,p)−cnt(a−b,p)即是$C^b_a$中p的个数, 所求答案即为$p_1^{sum_1}×p_2^{sum_2}×⋯×p_i^{sum_i}$.

### [889. 满足条件的01序列](https://www.acwing.com/problem/content/891/)

**解题思路:** 卡特兰数

卡特兰数为: $\frac{C^n_{2n}}{n+1}=\frac 1{n+1}×\frac{a×(a−1)×…×(a−b+1)}{1×2×…×b}\ (a=2n, b=n)$.

符合要求的路径必须严格在上图中红色线的下面(不可以碰到图中的红线, 可以碰到绿线). 则我们考虑任意一条不合法路径, 例如下图：

![image-20210416105556735.png](https://www.rearwaves.com/usr/assets/algorithm/math/61813_0e754fd29e-image-20210416105556735.png)

所有路径的条数为 $C^n_{2n}$, 其中不合法的路径有 $C^{n−1}_{2n}$ 条, 因此合法路径有：

推导完毕.

因为mod是质数, 因此任何数与mod都互质, 可以使用快速幂求逆元, 否则需要使用扩展欧几里得算法求逆元.

# 9 容斥原理

**容斥原理：**

对于$S_1, S_2, S_3,$有如下公式：

$$
S_1\cup S_2\cup S_3 = S_1+S_2+S_3 − S_1∩S_2 − S_1∩S_3 − S_2∩S_3 + S_1∩S_2∩S_3一般的,
$$

一般的,  设U中元素有n种不同的属性, 而第i种属性称为P~i~拥有属性P~i~的元素构成集合S~i~,那么:

即: $\left|\bigcup_{i=1}^{n} S_{i}\right|=\sum_{m=1}^{n}(-1)^{m-1} \sum_{a_{i}<a_{i+1}}\left|\bigcap_{i=1}^{m} S_{a_{i}}\right|$.

### [890. 能被整除的数](https://www.acwing.com/problem/content/892/)

给定一个整数 n 和 m 个不同的质数 $p_1,p_2,…,p_m$.

请你求出 1∼n 中能被 $p_1,p_2,…,p_m$ 中的至少一个数整除的整数有多少个.

**解题思路: **

样例: n = 10, p1=2,p2=3, 求1-10中能满足能整除p1或p2的个数, 即`2, 3, 4, 6, 8, 9, 10`,共7个.

记S~i~为1~n 中能整除p~i~的集合,那么根据容斥原理, 所有数的个数为各个集合的并集, 计算公式如下:

以题目样例为例: S1={2,4,6,8,10},S2={3,6,9},S1⋂S2={6},故S1⋃S2={2,3,4,6,8,9,10}.

**实现思路: **

```c++
const int N = 20;
int n, m;
int p[N];

# 10 简单博弈论

## 10.1 Nim游戏

必胜状态, 先手进行某一个操作, 留给后手是一个必败状态时, 对于先手来说是一个必胜状态. 即先手可以走到某一个必败状态.

必败状态, 先手无论如何操作, 留给后手都是一个必胜状态时, 对于先手来说是一个必败状态. 即先手走不到任何一个必败状态.

### [891. Nim游戏](https://www.acwing.com/problem/content/893/)

给定 n 堆石子, 两位玩家轮流操作, 每次操作可以从任意一堆石子中拿走任意数量的石子(可以拿完, 但不能不拿), 最后无法进行操作的人视为失败.

问如果两人都采用最优策略, 先手是否必胜.

**解题思路: **

假设 n 堆石子, 石子数目分别是 $a_{1}, a_{2}, \ldots, a_{n}$, 如果 $a_{1} \oplus a_{2} \oplus \ldots \oplus a_{n} \neq 0$, 先手必胜; 否则先手必败.

**证明:**

```c++
int main() {
	int n, res = 0;
	scanf("%d", &n);
	while (n--) {
		int x;
		scanf("%d", &x);
		res ^= x;
	}
	if (res) puts("Yes");
	else puts("No");
	return 0;
}
```

### [892. 台阶-Nim游戏](https://www.acwing.com/problem/content/894/)

问如果两人都采用最优策略, 先手是否必胜.

**解题思路:**

**最示始的情形:**

n=1 , 台阶数为 1 , 显然, 和简单 Nim 游戏相同, 当 $x{0} \neq 0$ 时, 先手必胜. 必胜策略：一次性全部拿走.

对于更复杂的情形, 最底层台阶一定和问题的解直接相关(游戏结束前, 必然为 $2 \rightarrow n$ 级台阶上的石子全空, 仅台阶1还剩余石子的情况).

**初止扩展:**

尝试分析 n=2 的情形:

$x_{1} \neq 0$ : 先手可以将第一级台阶的石子全部放在地上, 此时后手只能从第二级台阶上拿; 不论后手从第二级台阶拿多.

**假设:**

(可以先扩展到 n=3 或 n=4 的情形继续观察, 更容易得出该假设结论)

**证明:**

对于后手:

由此推知, 初始状态下:

- 各奇数级台阶的石子数异或和为 0 , 则先手必败;
- 各奇数级台阶的石子数异或和不为 0 , 则先手必胜.

## 10.2 SG函数

**Mex运算:** 设S表示一个非负整数集合. 定义mex(S)为求不出属于集合S的最小非负整数的运算, 即：$mex(S)=min(x)$, x属于自然数, 且x不属于S.

特别的, 整个有向图游戏G的SG函数值被定义为有向图游戏起点s的SG函数值, 即：$SG(G)=SG(s)$.

有向图游戏的和SG函数在数值上等于它所包含的各个子游戏SG函数的异或和, 即：$SG(G)=SG(G1)⨁SG(G2)⨁…⨁SG(Gm)$.

### [893. 集合-Nim游戏](https://www.acwing.com/problem/content/895/)

问如果两人都采用最优策略, 先手是否必胜.

**解题思路：**

对于n个图, 如果$SG(G1)⨁SG(G2)⨁…⨁SG(GN)≠0$, 则先手必胜, 否则先手必败.

h[i]表示的是每一堆石子有多少个, 将每一个h[i]看做一张有向图. 例如S=[2,5],h[1]=10. 看h[1]这张有向图：

![nimyx2.png](https://www.rearwaves.com/usr/assets/algorithm/math/49357_f3eded9d39-nimyx2.png)

**定理 1 ：**如果一个有向图游戏 G 的 SG 函数值为 0 那么先手必败, 否则先手必胜.

**定理 2 ：**如果有 n 个游戏同时进行, 那么若 $SG(G1)\ xor\ SG(G2)\ xor … xor\ SG(Gn)==0$, 那么先手必败, 否则先手必胜.

证明: (类似于 Nim 游戏的证明)如果 `xor==0` 那么无论怎么拿, 拿完后 xor 总不等于 0, 所以若 `xor==0` 那么总会把必胜节点留给对手, 所以先手必败.

### [894. 拆分-Nim游戏](https://www.acwing.com/problem/content/896/)

问如果两人都采用最优策略, 先手是否必胜.

**解题思路:**

注意：因为这题中原堆拆分成的两个较小堆小于原堆即可, 因此任意一个较小堆的拆分情况会被完全包含在较大堆中, 因此 S 可以开全局.

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

基础数学知识

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款