4. 基础数学初识
4.1 质数
概念
- 质数又称素数，一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数（规定1既不是质数也不是合数）
4.1.1 试除法判定质数
思想
- N<2
- 从i=2开始枚举，直到\sqrt{n}，若i能被N整除，说明不是质数
- 反之，则为质数
模板
bool is_prime(int n){
if(n<2) return 0; //若小于2直接返回false
for(int i=2;i<=n/i;i++){ //优化为sqrt(n)
if(n%i==0) return 0;
}
return 1;
}例题 866. 试除法判定质数
描述
给定 n 个正整数 ai，判定每个数是否是质数。
输入格式 第一行包含整数 n。
接下来 n 行，每行包含一个正整数 ai。
输出格式 共 n 行，其中第 i 行输出第 i 个正整数 ai 是否为质数，是则输出 Yes，否则输出 No。
数据范围 1≤n≤100, 1≤ai≤2^31−1 输入样例：
2
2
6输出样例：
Yes
No代码
#include <bits/stdc++.h>
using namespace std;
bool is_prime(int n){
if(n<2) return 0;
for(int i=2;i<=n/i;i++){
if(n%i==0) return 0;
}
return 1;
}
int main(){
int t;
cin>>t;
while(t--){
int x;
cin>>x;
if(is_prime(x)) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}4.1.2 分解质因数
概念
思想
- 算术基本定理：任何一个大于1的自然数N,如果N不为质数
- 那么N可以唯一分解成有限个质数的乘积N=p_1^{a_1}\times p_2^{a_2}\dots\times p_i^{a_k},且最多只有一个大于\sqrt{n}的质因子
- 这里p_1<p_2<p_3\dots p_ia_k是正整数
模板
map<int,int> primes; //存储质因子底数和其指数的映射
void get_div(int n){
primes.clear(); //清空数据
for(int i=2;i<=n/i;i++){ //从2开始枚举质因子
if(n%i==0){ //当其为质因子时
while(n%i==0){
primes[i]++; //指数增加
n/=i;
}
}
}
if(n>1) primes[n]++; //剩余的数大于1则为最后的质因子
}例题 867. 分解质因数
描述
给定 n 个正整数 ai，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。
输入格式 第一行包含整数 n。
接下来 n 行，每行包含一个正整数 ai。
输出格式 对于每个正整数 ai，按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。
每个正整数的质因数全部输出完毕后，输出一个空行。
数据范围 1≤n≤100, 2≤ai≤2×109 输入样例：
2
6
8输出样例：
2 1
3 1
2 3代码
#include <bits/stdc++.h>
using namespace std;
map<int,int> primes;
void get_div(int n){
primes.clear();
for(int i=2;i<=n/i;i++){
if(n%i==0){
while(n%i==0){
primes[i]++;
n/=i;
}
}
}
if(n>1) primes[n]++;
}
int main(){
int n;
cin>>n;
while(n--){
int x;
cin>>x;
get_div(x);
for(auto &p : primes) cout<<p.first<<" "<<p.second<<endl;
cout<<endl;
}
return 0;
}4.1.3 线性筛法求质数
思想
- 对于1\sim N中的一个合数n
- 从小到大枚举筛选出的质数p，将1\sim N范围内质数p的倍数的合数筛掉
- 从而保证了n只会被其最小质因子p_j筛掉，且一定会在枚举到p_j\times\frac{n}{p_j}之前筛掉
模板
int cnt; //记录质数个数
int primes[N]; //存储当前筛选出的质数
bool vis[N]; //标记是否被筛掉
void get_primes(int n){
for(int i=2;i<=n;i++){ //外层从2~n迭代
if(!vis[i]) primes[cnt++]=i; //没有被筛掉说明是质数，记录到primes[N]中
for(int j=0;primes[j]<=n/i;j++){ //将1~n范围内质数primes[j]的i倍的合数筛掉
vis[primes[j]*i]=1; //用最小质因子primes[j]筛掉合数
if(i%primes[j]==0) break;
//i%primes[j]!=0 : 说明primes[j] < i的所有质因子，故primes[j]是primes[j]*i的最小质因子
//i%primes[j]==0 : 说明从小到大枚举到此时的primes[j]，一定是i的最小质因子
}
}
}例题 868. 筛质数
描述
给定一个正整数 n，请你求出 1∼n 中质数的个数。
输入格式 共一行，包含整数 n。
输出格式 共一行，包含一个整数，表示 1∼n 中质数的个数。
数据范围 1≤n≤106 输入样例：
8输出样例：
4代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+3;
int cnt; //记录质数个数
int primes[N]; //存储当前筛选出的质数
bool vis[N]; //标记是否被筛掉
void get_primes(int n){
for(int i=2;i<=n;i++){ //外层从2~n迭代
if(!vis[i]) primes[cnt++]=i; //没有被筛掉说明是质数，记录到primes[N]中
for(int j=0;primes[j]<=n/i;j++){ //将1~n范围内质数primes[j]的i倍的合数筛掉
vis[primes[j]*i]=1; //用最小质因子primes[j]筛掉合数
if(i%primes[j]==0) break;
//i%primes[j]!=0 : 说明primes[j] < i的所有质因子，故primes[j]是primes[j]*i的最小质因子
//i%primes[j]==0 : 说明从小到大枚举到此时的primes[j]，一定是i的最小质因子
}
}
}
int main(){
int n;
cin>>n;
get_primes(n);
cout<<cnt<<endl;
return 0;
}4.2 约数
概念
- 约数，又称因数。整数a除以整数b(b≠0) 除得的商正好是整数而没有余数，我们就说a能被b整除，或b能整除a。a称为b的倍数，b称为a的约数。
4.2.1 试除法求约数
思想
- 从i=1开始枚举到\sqrt{N}
- i和\frac{N}{i}即为N的约数
模板
const int N=1e6+3;
int res[N]; //存储约数
int cnt; //记录数量
void get_div(int n){
cnt=0; //初始化
for(int i=1;i<=n/i;i++){ //从1开始枚举
if(n%i==0){
res[cnt++]=i; //将i作为约数
if(i!=n/i) res[cnt++]=n/i; //将n/i作为约数
}
}
sort(res,res+cnt); //将约数从小到大排序
}例题 869. 试除法求约数
描述
给定 n 个正整数 ai，对于每个整数 ai，请你按照从小到大的顺序输出它的所有约数。
输入格式 第一行包含整数 n。
接下来 n 行，每行包含一个整数 ai。
输出格式 输出共 n 行，其中第 i 行输出第 i 个整数 ai 的所有约数。
数据范围 1≤n≤100, 2≤ai≤2×109 输入样例：
2
6
8输出样例：
1 2 3 6
1 2 4 8 代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+3;
int res[N];
int cnt;
void get_div(int n){
cnt=0;
for(int i=1;i<=n/i;i++){
if(n%i==0){
res[cnt++]=i;
if(i!=n/i) res[cnt++]=n/i;
}
}
sort(res,res+cnt);
}
int main(){
int n;
cin>>n;
while(n--){
int x;
cin>>x;
get_div(x);
for(int i=0;i<cnt;i++) cout<<res[i]<<" ";
cout<<endl;
}
return 0;
}4.2.2 约数个数
思想
- 算术基本定理：任何一个大于1的自然数N,如果N不为质数
- 那么N可以唯一分解成有限个质数的乘积N=p_1^{a_1}\times p_2^{a_2}\dots\times p_i^{a_k},且最多只有一个大于\sqrt{n}的质因子
- 这里p_1<p_2<p_3\dots p_na_i是正整数
- 设d为N的任意一个约数，d=p_1^{b_1}\times p_2^{b_2}\dots\times p_i^{b_j}，其中0<b_j<a_k
- 由算术基本定理可知对于d中的p_i^{b_j}项，b_j取值不同，则d不同(每个数的因式分解是唯一的)
- =d的个数=b_j
- 根据乘法原理可知：N的约数个数为(a_1+1)\times(a_2+1)\times(a_3+1)\times\dots\times(a_k+1)
模板例题 870. 约数个数
描述
给定 n 个正整数 ai，请你输出这些数的乘积的约数个数，答案对 109+7 取模。
输入格式 第一行包含整数 n。
接下来 n 行，每行包含一个整数 ai。
输出格式 输出一个整数，表示所给正整数的乘积的约数个数，答案需对 109+7 取模。
数据范围 1≤n≤100, 1≤ai≤2×109 输入样例：
3
2
6
8输出样例：
12代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=1e9+7;
LL cnt=1;
map<int,int> primes; //存储质因子底数和其指数的映射
void get_div(int n){
for(int i=2;i<=n/i;i++){ //从2开始枚举质因子
if(n%i==0){ //当其为质因子时
while(n%i==0){
primes[i]++; //指数增加
n/=i;
}
}
}
if(n>1) primes[n]++; //剩余的数大于1则为最后的质因子
}
int main(){
int n;
cin>>n;
while(n--){
int x;
cin>>x;
get_div(x);
}
for(auto &p : primes) cnt=cnt*(p.second+1)%mod; //核心：N的约数个数为(a1+1)*(a2+1)*(a3+1)*…*(ai+1)
cout<<cnt<<endl;
return 0;
}4.2.3 约数之和
思想
- 算术基本定理：任何一个大于1的自然数N,如果N不为质数
- 那么N可以唯一分解成有限个质数的乘积N=p_1^{a_1}\times p_2^{a_2}\dots\times p_i^{a_k},且最多只有一个大于\sqrt{n}的质因子
- 这里p_1<p_2<p_3\dots p_ia_k是正整数
- 根据乘法原理可知：N的约数之和=(p_1^{0}+p_1^{1}+\dots+p_1^{a_1})\times(p_2^{0}+p_2^{1}+\dots+p_2^{a_2})\times\dots\times(p_i^{0}+p_i^{1}+\dots+p_i^{a_k})
模板例题 871. 约数之和
描述
给定 n 个正整数 ai，请你输出这些数的乘积的约数之和，答案对 109+7 取模。
输入格式 第一行包含整数 n。
接下来 n 行，每行包含一个整数 ai。
输出格式 输出一个整数，表示所给正整数的乘积的约数之和，答案需对 109+7 取模。
数据范围 1≤n≤100, 1≤ai≤2×109 输入样例：
3
2
6
8输出样例：
252代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=1e9+7;
LL res=1;
map<int,int> primes; //存储质因子底数和其指数的映射
void get_div(int n){
for(int i=2;i<=n/i;i++){ //从2开始枚举质因子
if(n%i==0){ //当其为质因子时
while(n%i==0){
primes[i]++; //指数增加
n/=i;
}
}
}
if(n>1) primes[n]++; //剩余的数大于1则为最后的质因子
}
int main(){
int n;
cin>>n;
while(n--){
int x;
cin>>x;
get_div(x);
}
for(auto &p : primes){
LL t=1;
int a=p.first,b=p.second;
while(b--){
t=(t*a+1)%mod; //核心：求出 p0一直加到p的k的次方的和
}
res=res*t%mod;
}
cout<<res<<endl;
return 0;
}4.2.4 最大公约数和最小公倍数
概念
- 最大公约数指两个或多个整数共有约（因）数中最大的数
- 最小公倍数指两个或多个整数的公倍数里最小的数
思想
- 辗转相除法求最大公约数 例如：假如需要求 100 和18 两个正整数的最大公约数,用欧几里得算法，是这样进行的： 100 / 18 = 5 (余 10) 18 / 10= 1(余8) 10 / 8 = 1(余2) 8 / 2 = 4 (余0) 至此，最大公约数为2 以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 100 和 18 的最大公约数2。
- 求N和M的最小公倍数lcm(N,M)，则先求N和M的最大公约数gcd(N,M)，然后\frac{N\times M}{gcd(N,M)}则为最小公倍数。
模板
//最大公约数
int gcd(int a, int b){
return b ? gcd(b, a % b) : a;
}
//最小公倍数
int lcm(int a,int b){
return a/gcd(a,b)*b;
}4.3 欧拉函数
概念
- 1∼N中与N互质的数的个数被称为欧拉函数，记为 \phi(N),特别的\phi(1)=1
- 欧拉函数是一个积性函数，若m，n互质，则有\phi(m\times n)=\phi(m)\times\phi(n)
4.3.1 公式法求欧拉函数
思想
- 算术基本定理：任何一个大于1的自然数N,如果N不为质数
- 那么N可以唯一分解成有限个质数的乘积N=p_1^{a_1}\times p_2^{a_2}\dots\times p_i^{a_k},且最多只有一个大于\sqrt{n}的质因子
- 这里p_1<p_2<p_3\dots p_ia_k是正整数
- 则\phi(N)=\phi(p_1^{a_1})\times\phi(p_2^{a_2})\times\dots\times\phi(p_n^{a_n})
- 对于任意一项\phi(p_i^{a_i}),与p_i^{a_i}不互质的数有p_i,2\times p_i,3\times p_i,\dots,p_i^{(a_i-1)}\times p_i共p_i^{(a_i-1)}项
- 即\phi(p_i^{a_i})=p_i^{a_i}-p_i^{(a_i-1)}
模板
typedef long long LL;
LL phi(LL n){
LL res=n;
for(int i=2;i<=n/i;i++){
if(n%i==0){
res=res/i*(i-1); //(1-1/i)转换为(i-1)/i
while(n%i==0) n/=i;
}
}
if(n>1) res=res/n*(n-1);
return res;
}例题 873. 欧拉函数
描述
给定 n 个正整数 ai，请你求出每个数的欧拉函数。
欧拉函数的定义 1∼N 中与 N 互质的数的个数被称为欧拉函数，记为 ϕ(N)。 若在算数基本定理中，N=pa11pa22…pamm，则： ϕ(N) = N×p1−1p1×p2−1p2×…×pm−1pm
输入格式 第一行包含整数 n。
接下来 n 行，每行包含一个正整数 ai。
输出格式 输出共 n 行，每行输出一个正整数 ai 的欧拉函数。
数据范围 1≤n≤100, 1≤ai≤2×109 输入样例：
3
3
6
8输出样例：
2
2
4代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL phi(LL n){
LL res=n;
for(int i=2;i<=n/i;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;
while(n--){
int x;
cin>>x;
cout<<phi(x)<<endl;
}
return 0;
}4.3.2 筛法求欧拉函数
思想
- 利用线性筛，在筛选1\sim N中的质数时，将1\sim N的欧拉函数\phi(P_i)求出
- 对于质数P_i,其\phi(P_i)=P\times(1-\frac{1}{P})=P-1
- 对于合数P_i,其\phi(P_i)=N\times\prod^{n}_{i=1}{(1-\frac{1}{p_i})}
- 在线性筛法求质数的模板中利用最小质因子筛掉合数的过程时： 当i\%primes[j]=0时，说明primes[j]是i的一个质因子，且primes[j]是primes[j]\times i的一个质因子，故\phi(i)包含(1-\frac{1}{primes[j]})的情况，即\phi(primes[j]\times i)=primes[j]\times\phi(i) 当i\%primes[j]\ne 0时 ，说明primes[j]是i的最小质因子，且primes[j]不是primes[j]\times i的一个质因子，故\phi(i)不包含(1-\frac{1}{primes[j]})的情况，即\begin{aligned}\phi(primes[j]\times i)&=primes[j]\times\phi(i)\times(1-\frac{1}{primes[j]})\ &=(primes[j]-1)\times\phi(i)\end{aligned}
模板
int primes[N]; //存储当前筛选出的质数
bool vis[N]; //标记是否被筛掉
int phi[N]; //记录欧拉函数的值
int cnt; //记录质数个数
void get_phi(int n){
phi[1]=1; //特别的，phi[1]=1
for(int i=2;i<=n;i++){
if(!vis[i]){
primes[cnt++]=i; //没有被筛掉说明是质数，记录到primes[N]中
phi[i]=i-1; //质数的欧拉函数的情况
}
for(int j=0;primes[j]<=n/i;j++){ //将1~n范围内质数primes[j]的i倍的合数筛掉
vis[primes[j]*i]=1;
if(i%primes[j]==0){ //用最小质因子primes[j]筛掉合数
phi[primes[j]*i]=primes[j]*phi[i]; //包含(1-1/primes[j])的情况
break;
}
else phi[primes[j]*i]=(primes[j]-1)*phi[i]; //不包含(1-1/primes[j])的情况
}
}
}例题 874. 筛法求欧拉函数
描述
给定一个正整数 n，求 1∼n 中每个数的欧拉函数之和。
输入格式 共一行，包含一个整数 n。
输出格式 共一行，包含一个整数，表示 1∼n 中每个数的欧拉函数之和。
数据范围 1≤n≤106 输入样例：
6输出样例：
12代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+3;
typedef long long LL;
int primes[N];
bool vis[N];
int phi[N];
int cnt;
void get_phi(int n){
phi[1]=1;
for(int i=2;i<=n;i++){
if(!vis[i]){
primes[cnt++]=i;
phi[i]=i-1;
}
for(int j=0;primes[j]<=n/i;j++){
vis[primes[j]*i]=1;
if(i%primes[j]==0){
phi[primes[j]*i]=primes[j]*phi[i];
break;
}
else phi[primes[j]*i]=(primes[j]-1)*phi[i];
}
}
}
int main(){
int n;
cin>>n;
get_phi(n);
LL res=0;
for(int i=1;i<=n;i++){
res+=phi[i];
}
cout<<res<<endl;
return 0;
}4.4 快速幂
概念
- 快速求出a^k\mod p的结果
思想
- 预处理出a^{2^0},a^{2^1},a^{2^2}\dots a^{2^{log_2^k}}的结果
- 则使得k=2^{p_1}+2^{p_2}+\dots+2^{p_i}
- 即：a^k=a^{2^{p_1}}\times a^{2^{p_2}}\times\dots\times a^{2^{p_i}}
- 对于a^{2^0}\times a^{2^0}=a^{2^{1}},a^{2^{1}}\times a^{2^{1}}=a^{2^{2}}，即a^{2^{p_i}}=a^{2^{p_{i-1}}}\times a^{2^{p_{i-1}}}
- 综上所述，在操作时记录a^{p_i}的值，和累乘的结果
- 将k化为二进制表示，按位>>操作，若当前位是1，则对当前累乘的结果\times a^{p_i} \mod p
- 每次对
进行按位>>操作后，更新
- 当二进制下的k无法再>>时，累乘结果即为答案
模板
typedef long long LL;
LL qmi(LL a,LL k,LL p){ //计算 a^k % p 的结果
LL res=1; //记录累乘结果
while(k){
if(k&1) res=res*a%p; //k&1得到当前位，若为1则累乘a^pi
a=a*a%p; //更新a^pi
k>>=1; //右移1位
}
return res;
}4.4.1 快速幂求逆元
概念
- 同余：设m为正整数，a和b是整数，若m|a-b，则称a模m同余于b，或a与b模m同余，记作a\equiv b(mod~m)
- 若ab\equiv 1(mod~m)，则称b为a的模m逆，记作a^{-1}(mod~m)或a^{-1}
注意
- a的模m逆存在 \Leftrightarrow a与m互质
- 当m为质数时，用费马小定理求
- 当m不为质数时，用扩展欧几里得算法求
思想
- 利用快速幂实现m为质数时用费马小定理求逆元
- 费马小定理：设p为素数，且a与p互质，则a^{p^{-1}}\equiv 1(mod~p)
模板例题 876. 快速幂求逆元
描述
给定 n 组 ai,pi，其中 pi 是质数，求 ai 模 pi 的乘法逆元，若逆元不存在则输出 impossible。
注意：请返回在 0∼p−1 之间的逆元。
乘法逆元的定义 若整数 b，m 互质，并且对于任意的整数 a，如果满足 b|a，则存在一个整数 x，使得 a/b≡a×x(modm)，则称 x 为 b 的模 m 乘法逆元，记为 b−1(modm)。 b 存在乘法逆元的充要条件是 b 与模数 m 互质。当模数 m 为质数时，bm−2 即为 b 的乘法逆元。
输入格式 第一行包含整数 n。
接下来 n 行，每行包含一个数组 ai,pi，数据保证 pi 是质数。
输出格式 输出共 n 行，每组数据输出一个结果，每个结果占一行。
若 ai 模 pi 的乘法逆元存在，则输出一个整数，表示逆元，否则输出 impossible。
数据范围 1≤n≤105, 1≤ai,pi≤2∗109 输入样例：
3
4 3
8 5
6 3输出样例：
1
2
impossible代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL qmi(LL a,LL k,LL p){
LL res=1;
while(k){
if(k&1) res=res*a%p;
a=a*a%p;
k>>=1;
}
return res;
}
int main(){
int n;
cin>>n;
while(n--){
int a,p;
cin>>a>>p;
if(a%p==0) cout<<"impossible"<<endl; //a与p不互质则说明无逆元
else cout<<qmi(a,p-2,p)<<endl;
}
return 0;
}4.5 扩展欧几里得算法
思想
- 欧几里得算法：gcd(a,b)=gcd(b,a\%b)，特别的gcd(a,0)=a
- 裴蜀定理：对于任意正整数a,b，一定存在非零的x,y，使得ax+by=gcd(a,b)
注意
- 当方程符合ax+by=gcd(a,b)的形式时，才可以用扩展欧几里得算法求解(x_0,y_0)
- 推论：可以进一步求解任意方程ax+by=n，得到一个整数解
模板
void exgcd(int a,int b,int &x,int &y){
if(!b){ //若b=0时
x=1,y=0;
return ;
}
else{ //b!=0时
exgcd(b,a%b,x,y); //递归到下一层
int t=x; //返回时执行
x=y;
y=t-a/b*y;
}
}例题 877. 扩展欧几里得算法
描述
给定 n 对正整数 ai,bi，对于每对数，求出一组 xi,yi，使其满足 ai×xi+bi×yi=gcd(ai,bi)。
输入格式 第一行包含整数 n。
接下来 n 行，每行包含两个整数 ai,bi。
输出格式 输出共 n 行，对于每组 ai,bi，求出一组满足条件的 xi,yi，每组结果占一行。
本题答案不唯一，输出任意满足条件的 xi,yi 均可。
数据范围 1≤n≤105, 1≤ai,bi≤2×109 输入样例：
2
4 6
8 18输出样例：
-1 1
-2 1代码
#include <bits/stdc++.h>
using namespace std;
void exgcd(int a,int b,int &x,int &y){
if(!b){
x=1,y=0;
return ;
}
else{
exgcd(b,a%b,x,y);
int t=x;
x=y;
y=t-a/b*y;
}
}
int main(){
int n;
cin>>n;
while(n--){
int a,b,x,y;
cin>>a>>b;
exgcd(a,b,x,y);
cout<<x<<" "<<y<<endl;
}
return 0;
}4.5.1 解一元线性同余方程
概念
- ax\equiv b(mod~m)，即\frac{ax}{m}与\frac{b}{m}的余数相同，且a,b,m为整数，求x的值
- 该方程即为一元线性同余方程
思想
- 对ax\equiv b(mod~m)做等价变形：ax+my=b
- 由扩展欧几里得算法的推论可知：当且仅当 gcd(a,m)可以整除b时，ax+my=b存在整数解
例题 878. 线性同余方程
描述
给定 n 组数据 ai,bi,mi，对于每组数求出一个 xi，使其满足 ai×xi≡bi(modmi)，如果无解则输出 impossible。
输入格式 第一行包含整数 n。
接下来 n 行，每行包含一组数据 ai,bi,mi。
输出格式
输出共 n 行，每组数据输出一个整数表示一个满足条件的 xi，如果无解则输出 impossible。
每组数据结果占一行，结果可能不唯一，输出任意一个满足条件的结果均可。
输出答案必须在 int 范围之内。
数据范围 1≤n≤105, 1≤ai,bi,mi≤2×109
2
2 3 6
4 3 5输出样例：
输出样例：
impossible
-3代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
void exgcd(LL a,LL b,LL &x,LL &y){
if(!b){ //若b=0时
x=1,y=0;
return ;
}
else{
exgcd(b,a%b,x,y);
LL t=x;
x=y;
y=t-a/b*y;
}
}
LL gcd(LL a,LL b){
return b ? gcd(b,a%b) : a;
}
int main(){
int n;
cin>>n;
while(n--){
LL a,b,m,x,y;
cin>>a>>b>>m;
LL d=gcd(a,m);
exgcd(a,m,x,y);
if(b%d) cout<<"impossible"<<endl;
else cout<<b/d*x%m<<endl;
}
return 0;
}4.6 中国剩余定理
概念
- 若存在整数m_1,m_2,m_3\dots m_n两两互质，则对于任意的整数a_1,a_2,a_3\dots a_n，一元线性同余方程组(S)有通解
思想
- 对于(S)其中的两个式子进行合并
- 将等价转换后的两式进行联立，化简得k_1m_1+k_2(-m_2)=a_2-a_1~①
- 由扩展欧几里得算法可以得到一组解({k_1}',{k_2}')，使得：{k_1}'m_1+{k_2}'(-m_2)=gcd(m_1,-m_2)
- 若gcd(m_1,-m_2)不能整除a2-a1，则无解，否则有通解
- 设gcd(m_1,-m_2)=d,y=\frac{(a_2-a_1)}{d}
- 由扩展欧几里得算法的推论可知：
- 引入通解\begin{cases}k_1={k_1}+k\frac{m_2}{d}\\k_2={k_2}+\frac{m_1}d\end{cases}，k\in Z
- 将通解带入①得({k_1}+k\frac{m_2}{d})m_1+({k_2}+k\frac{m_1}{d})(-m_2)=a_2-a_1
- 化简得k_1m_1+k_2(-m_2)=a_2-a_1和①相同，故成立
- 重复上述步骤，不断合并剩余的式子，即可得到最终的通解
例题 204. 表达整数的奇怪方式
描述
给定 2n 个整数 a1,a2,…,an 和 m1,m2,…,mn，求一个最小的非负整数 x，满足 ∀i∈[1,n],x≡mi(mod ai)。
输入格式 第 1 行包含整数 n。
第 2…n+1 行：每 i+1 行包含两个整数 ai 和 mi，数之间用空格隔开。
输出格式 输出最小非负整数 x，如果 x 不存在，则输出 −1。 如果存在 x，则数据保证 x 一定在 64 位整数范围内。
数据范围 1≤ai≤231−1, 0≤mi<ai 1≤n≤25 输入样例：
2
8 7
11 9输出样例：
31代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
void exgcd(LL a,LL b, LL &x,LL &y){
if(!b){
x=1,y=0;
return ;
}
else{
exgcd(b,a%b,x,y);
LL t=x;
x=y;
y=t-a/b*y;
}
}
LL gcd(LL a,LL b){
return b ? gcd(b,a%b) : a;
}
int main(){
int n;
cin>>n;
LL x=0,m1,a1; //第一个方程的系数 备份数据
cin>>m1>>a1; //先输入第一个方程
for(int i=0;i<n-1;i++){ //合并接下来的n-1个方程
LL m2,a2;
cin>>m2>>a2;
LL k1,k2;
LL d=gcd(m1,m2);
exgcd(m1,m2,k1,k2);
if((a2-a1)%d){ //此时无解
x=-1;
break;
}
k1*=(a2-a1)/d;//特解
k1=(k1%(m2/d)+m2/d)%(m2/d); //让特解k1取到最小正整数解
x=k1*m1+a1;
LL m=abs(m1/d*m2);
a1=k1*m1+a1;
m1=m;
}
if(x!=-1) x=(a1%m1+m1)%m1 //当循环结束时，此时的值应该与最小公倍数取模,以求得最小正整数解
cout<<x<<endl;
return 0;
}4.7 高斯消元
概念
- 利用初等行（列）变换，对一组线性方程组进行消元，把增广矩阵化为阶梯型矩阵
初等行（列）变换
- 某一行乘上一个非零数，矩阵不变
- 某一行乘上一个常数加到另一行上，矩阵不变
- 交换矩阵中某两行的元素，矩阵不变
思想
- 对增广矩阵的每一列c_i进行枚举，找到当前的列中绝对值最大的元素所在的行r_i
- 将r_i行与最上方未确定阶梯型的行进行交换
- 用初等行变换将r_i行变为原来的k倍，且使得变换后， r_i行的第一个数变成1
- 继续用初等行变换，将r_i行下方的所有的行的c_i列的值变为0
- 重复上述步骤，直到最终得到阶梯型矩阵，判断解的情况
- 若有解，则从最后一行向上回代，得出方程组的解
模板
const int N=110;
const double eps=1e-8;
int n;
double a[N][N];
int gauss(){
int c,r;
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; //正对角线中有元素为0,这时有无穷解和无解
if(t!=r) for(int i=c;i<=n;i++) swap(a[t][i],a[r][i]); //若t改变，则交换两行
for(int i=n;i>=c;i--) a[r][i]/=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){ //row<n,即对角线中元素为0的行未被算上
for(int i=r;i<n;i++){
if(fabs(a[i][n])>eps) return 2;
}
return 1;
}
for(int i=n-1;i>=0;i--){ //将非主元位置的A系数矩阵的其他x消去
for(int j=i+1;j<n;j++) a[i][n]-=a[j][n]*a[i][j];
}
return 0;
}4.7.1 高斯消元解线性方程组
模板例题 883. 高斯消元解线性方程组
描述
输入一个包含 n 个方程 n 个未知数的线性方程组。
方程组中的系数为实数。
求解这个方程组。
下图为一个包含 m 个方程 n 个未知数的线性方程组示例：
输入格式 第一行包含整数 n。
接下来 n 行，每行包含 n+1 个实数，表示一个方程的 n 个系数以及等号右侧的常数。
输出格式 如果给定线性方程组存在唯一解，则输出共 n 行，其中第 i 行输出第 i 个未知数的解，结果保留两位小数。
如果给定线性方程组存在无数解，则输出 Infinite group solutions。
如果给定线性方程组无解，则输出 No solution。
数据范围 1≤n≤100, 所有输入系数以及常数均保留两位小数，绝对值均不超过 100。
输入样例：
3
1.00 2.00 -1.00 -6.00
2.00 1.00 -3.00 -9.00
-1.00 -1.00 2.00 7.00输出样例：
1.00
-2.00
3.00分析
代码
#include <bits/stdc++.h>
using namespace std;
const int N=110;
const double eps=1e-8;
int n;
double a[N][N];
int gauss(){
int c,r;
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; //正对角线中有元素为0,这时有无穷解和无解
if(t!=r) for(int i=c;i<=n;i++) swap(a[t][i],a[r][i]); //若t改变，则交换两行
for(int i=n;i>=c;i--) a[r][i]/=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){ //row<n,即对角线中元素为0的行未被算上
for(int i=r;i<n;i++){
if(fabs(a[i][n])>eps) return 2;
}
return 1;
}
for(int i=n-1;i>=0;i--){ //将非主元位置的A系数矩阵的其他x消去
for(int j=i+1;j<n;j++) a[i][n]-=a[j][n]*a[i][j];
}
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){
cout<<"No solution"<<endl;
}
else if(t==1) cout<<"Infinite group solutions"<<endl;
else{
for(int i=0;i<n;i++){
if(fabs(a[i][n])<eps) a[i][n]=0;
printf("%.2lf\n",a[i][n]);
}
}
return 0;
}4.7.2 高斯消元解异或线性方程组
思想
- 将解线性方程组的计算化为异或运算
模板例题 884. 高斯消元解异或线性方程组
描述
输入一个包含 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。
输入格式 第一行包含整数 n。
接下来 n 行，每行包含 n+1 个整数 0 或 1，表示一个方程的 n 个系数以及等号右侧的常数。
输出格式 如果给定线性方程组存在唯一解，则输出共 n 行，其中第 i 行输出第 i 个未知数的解。
如果给定线性方程组存在多组解，则输出 Multiple sets of solutions。
如果给定线性方程组无解，则输出 No solution。
数据范围 1≤n≤100 输入样例：
3
1 1 0 1
0 1 1 0
1 0 0 1输出样例：
1
0
0代码
#include <bits/stdc++.h>
using namespace std;
const int N=110;
int n;
int a[N][N];
int guass(){
int c,r;
for (c=0,r=0;c<n;c++){
int t=r;
for (int i=r;i<n;i++){
if (a[i][c]) t = i;
}
if(!a[t][c]) continue;
for (int i=c;i<=n;i++) swap(a[r][i],a[t][i]);
for (int i=r+1;i<n;i++){
if (a[i][c]){
for (int j=n;j>=c;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 t=guass();
if(t==0){
for(int i=0;i<n;i++) cout<<a[i][n]<<endl;
}
else if(t==1) cout<<"Multiple sets of solutions"<<endl;
else cout<<"No solution"<<endl;
return 0;
}4.8 组合数
概念
- 从n个不同元素中每次取出m个不同元素，不管其顺序合成一组，称为从n个元素中不重复地选取m个元素的一个组合。
- 所有这样的组合的种数称为组合数
公式
- C_{n}^{m}=\frac{n!}{m!(n-m)!},C_n^0=C_n^n=1
- C_n^m=C_n^{n-m}
- C_n^0+C_n^1+C_n^2+\dots+C_n^n=2^n
4.8.1 求组合数 I
思想
- 递推公式求组合数
模板例题 885. 求组合数 I
给定 n 组询问，每组询问给定两个整数 a，b，请你输出 Cbamod(109+7) 的值。
输入格式 第一行包含整数 n。
接下来 n 行，每行包含一组 a 和 b。
输出格式 共 n 行，每行输出一个询问的解。
数据范围 1≤n≤10000, 1≤b≤a≤2000 输入样例：
3
3 1
5 3
2 2输出样例：
3
10
1代码
#include <bits/stdc++.h>
using namespace std;
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; //如果j = 0，那么把c[i][j]初始化为1
else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod; //递推式
}
}
}
int main(){
init();
int n;
cin>>n;
while(n--){
int a,b;
cin>>a>>b;
cout<<c[a][b]<<endl;
}
return 0;
}4.8.2 求组合数 II
思想
- C_{n}^{m}=\frac{n!}{m!(n-m)!}=n!\times(m!(n-m)!)^{-1}=n!\times m!^{-1}\times (n-m)!^{-1}
- 预处理fact[N]和infact[N]，fact[i]存储i!，infact[i]存储i!^{-1}
- 则C_n^m=fact[n]*infact[m]*infact[n-m]
- 预处理时利用快速幂求逆元\pmod {1e9+7}
模板例题 886. 求组合数 II
描述
给定 n 组询问，每组询问给定两个整数 a，b，请你输出 Cbamod(109+7) 的值。
输入格式 第一行包含整数 n。
接下来 n 行，每行包含一组 a 和 b。
输出格式 共 n 行，每行输出一个询问的解。
数据范围 1≤n≤10000, 1≤b≤a≤105 输入样例：
3
3 1
5 3
2 2输出样例：
3
10
1代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+3,mod=1e9+7;
LL fact[N],infact[N];
LL qmi(LL a,LL k,LL p){
int res=1;
while(k){
if(k&1) res=res*a%p;
a=a*a%p;
k>>=1;
}
return res;
}
int main(){
fact[0]=infact[0]=1;
for(int i=1;i<N;i++){
fact[i]=fact[i-1]*i%mod; //存储i!
infact[i]=infact[i-1]*qmi(i,mod-2,mod)%mod; //qmi(i,mod-2,mod)快速幂求逆元
}
LL n;
cin>>n;
while(n--){
LL a,b;
cin>>a>>b;
cout<<fact[a]*infact[b]%mod*infact[a-b]%mod<<endl; //计算公式
}
return 0;
}4.8.3 求组合数 III
思想
- 卢卡斯定理：
模板例题
描述
给定 n 组询问，每组询问给定三个整数 a,b,p，其中 p 是质数，请你输出 Cbamodp 的值。
输入格式 第一行包含整数 n。
接下来 n 行，每行包含一组 a,b,p。
输出格式 共 n 行，每行输出一个询问的解。
数据范围 1≤n≤20, 1≤b≤a≤1018, 1≤p≤105,
输入样例：
3
5 3 7
3 1 5
6 4 13输出样例：
3
3
2代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL qmi(LL a,LL k,LL p){
LL res=1;
while(k){
if(k&1) res=res*a%p;
a=a*a%p;
k>>=1;
}
return res;
}
LL C(LL a,LL b,LL p){
if(b>a) return 0;
LL res=1;
for(LL i=1,j=a;i<=b;i++,j--){
res=res*j%p;
res=res*qmi(i,p-2,p)%p;
}
return res;
}
LL lucas(LL a,LL b,LL p){
if(a<p&&b<p) return C(a,b,p);
return C(a%p,b%p,p)*lucas(a/p,b/p,p)%p;
}
int main(){
int n;
cin>>n;
while(n--){
LL a,b;
LL p;
cin>>a>>b>>p;
cout<<lucas(a,b,p)<<endl;
}
return 0;
}4.8.4 求组合数 IV
思想
- 利用高精度存储所有的方案数
模板例题 888. 求组合数 IV
描述
输入 a,b，求 Cba 的值。
注意结果可能很大，需要使用高精度计算。
输入格式 共一行，包含两个整数 a 和 b。
输出格式 共一行，输出 Cba 的值。
数据范围 1≤b≤a≤5000
5 3输出样例：
输出样例：
10代码
#include <bits/stdc++.h>
using namespace std;
const int N=5010;
int primes[N];
int sum[N];
bool vis[N];
int cnt;
void get_primes(int n){
for(int i=2;i<=n;i++){
if(!vis[i]) primes[cnt++]=i;
for(int j=0;primes[j]<=n/i;j++){
vis[primes[j]*i]=1;
if(i%primes[j]==0) break;
}
}
}
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(a-b,p)-get(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]);
}
}
for(int i=res.size()-1;i>=0;i--) cout<<res[i];
return 0;
}4.9 容斥原理
思想
- 求
的面积：
- 推广求
的面积：
- 若将面积作为集合看待，则容易推出：
模板例题 890. 能被整除的数
给定一个整数 n 和 m 个不同的质数 p1,p2,…,pm。
请你求出 1∼n 中能被 p1,p2,…,pm 中的至少一个数整除的整数有多少个。
输入格式 第一行包含整数 n 和 m。
第二行包含 m 个质数。
输出格式 输出一个整数，表示满足条件的整数的个数。
数据范围 1≤m≤16, 1≤n,pi≤109 输入样例：
10 2
2 3输出样例：
7代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=20;
int p[N];
int main(){
int n,m;
cin>>n>>m;
for(int i=0;i<m;i++) cin>>p[i];
LL res=0;
for(int i=1;i<1<<m;i++){ // 1~2^m-1这些数代表2^m-1个不同的项
LL t=1,s=0; //s代表当前枚举的项中包含集合的个数
for(int j=0;j<m;j++){ //看这个项的第 j 位是否包含，1代表包含，0代表不包含
if(i>>j&1){ //选
if(t*p[j]>n){ //此时 n/t = 0，直接break即可
t=-1;
break;
}
t*=p[j];
s++;
}
}
if(t!=-1){
if(s%2) res+=n/t; //加奇数项的个数
else res-=n/t; //减偶数项的个数
}
}
cout<<res<<endl;
return 0;
}4.10 博弈论
概念
若一个游戏满足：
- 由两名玩家交替行动
- 在游戏进行的任意时刻，可以执行的合法行动与轮到哪位玩家无关
- 不能行动的玩家判负
则称该游戏为一个公平组合游戏
尼姆游戏（NIM）属于公平组合游戏，但常见的棋类游戏，比如围棋就不是公平组合游戏，因为围棋交战双方分别只能落黑子和白子，胜负判定也比较负责，不满足条件2和3
4.10.1 Nim 游戏
游戏规则
给定n堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。 问如果两人都采用最优策略，先手是否必胜。
例如：有两堆石子，第一堆有2个，第二堆有3个，先手必胜。
操作步骤
- 先手从第二堆拿走1个，此时第一堆和第二堆数目相同
- 无论后手怎么拿，先手都在另外一堆石子中取走相同数量的石子即可
思想
- 必胜状态：先手进行某一个操作，留给后手是一个必败状态时，对于先手来说是一个必胜状态。即先手可以走到某一个必败状态
- 必败状态：先手无论如何操作，留给后手都是一个必胜状态时，对于先手来说是一个必败状态。即先手走不到任何一个必败状态
- 结论：假设有
堆石子，数目分别是
，如果
，先手必胜；否则先手必败。
证明
- 操作到最后时，每堆石子数都是0，即：0\oplus 0\oplus\dots\oplus0=0
- 在操作过程中，如果a_1\oplus a_2\oplus\dots\oplus a_n=x\ne 0，那么玩家必然可以通过拿走某一堆若干个石子将异或结果变为0 \begin{aligned} 证明：&\\ &设x的二进制表示中最高一位1在第k位\\ &则a_1,a_2,\dots,a_n中，必然有一个数a_i，它的第k为1\\ &且一定满足:a_i\oplus x\lt a_i\\ &若从第i堆石子中拿走(a_i−a_i\oplus x)个石子\\ &则第i石子还剩a_i−(a_i−a_i\oplus x)==a_i\oplus x个石子\\ &由：a_1\oplus a_2\oplus\dots\oplus a_i \oplus\dots a_n=x\ne 0可知\\ &此时：a_1\oplus a_2\oplus\dots\oplus a_i\oplus x \oplus\dots a_n=x\oplus x=0 \end{aligned}
- 在操作过程中，如果a_1\oplus a_2\oplus\dots\oplus a_n=x=0，那么无论玩家怎么拿，必然会导致最终异或结果不为0 \begin{aligned} 反证明：&\\ &假设玩家从第i堆石子拿走若干个，结果仍是0\\ &不妨设拿走后，第i堆还剩下a'个石子，且a'\lt a_i\\ &此时仍有：a_1\oplus a_2\oplus\dots\oplus a'\oplus\dots a_n=0\\ &则有(a_1\oplus a_2\oplus\dots\oplus a'\oplus\dots a_n)=(a_1\oplus a_2\oplus\dots\oplus a_i\oplus\dots a_n)=a'\oplus a_i=0\\ &即：a'=a_i，与原假设a'\lt a_i矛盾\\ &故假设不成立 \end{aligned}
- 综上：若先手面对的局面是a_1\oplus a_2\oplus\dots\oplus a_n\ne 0，则先手必胜，反之先手必败
模板例题 891. Nim游戏
描述
给定 n 堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。
输入格式 第一行包含整数 n。
第二行包含 n 个数字，其中第 i 个数字表示第 i 堆石子的数量。
输出格式
如果先手方必胜，则输出 Yes。
否则，输出 No。
数据范围 1≤n≤105, 1≤每堆石子数≤109 输入样例：
2
2 3输出样例：
Yes代码
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
int res;
cin>>res;
for(int i=0;i<n-1;i++){
int m;
cin>>m;
res^=m;
}
if(res) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
}4.10.2 台阶-Nim 游戏
描述
现在，有一个 n 级台阶的楼梯，每级台阶上都有若干个石子，其中第 i 级台阶上有 ai 个石子(i≥1)。
两位玩家轮流操作，每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中（不能不拿）。
已经拿到地面上的石子不能再拿，最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。
输入格式 第一行包含整数 n。
第二行包含 n 个整数，其中第 i 个整数表示第 i 级台阶上的石子数 ai。
输出格式
如果先手方必胜，则输出 Yes。
否则，输出 No。
数据范围 1≤n≤105, 1≤ai≤109 输入样例：
3
2 1 3输出样例：
Yes分析
- 在采取最优策略的情况下，一方玩家对于偶数级台阶的操作的影响，可以被另一方玩家做相同操作的结果消去
- 故只考虑奇数级台阶的情况，适用于经典
Nim游戏 - 即：对于奇数级台阶，若先手面对的局面是a_1\oplus a_3\oplus\dots\oplus a_n\ne 0，则先手必胜，反之先手必败
代码
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
int res;
cin>>res;
for(int i=2;i<=n;i++){
int m;
cin>>m;
if(i%2) res^=m;
}
if(res) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
}4.10.3 集合-Nim 游戏
游戏规则
给定n堆石子以及一个由k个不同正整数构成的数字集合S。
现在有两位玩家轮流操作，每次操作可以从任意一堆石子中拿取石子，每次拿取的石子数量必须包含于集合S，最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。
核心思想
- Mex运算：设S表示一个非负整数集合，定义Mex(S)为求出不属于集合S的最小自然数运算，例如：S={0,1,2,4}，则Mes(S)=3
- SG函数：在有向图游戏中，对于每个节点x,设从x出发共有k条有向边，分别到达节点y_1,y_2\dots y_k，定义SG(x)的后记节点y_1,y_2\dots y_k的SG函数值构成的集合在执行Mex运算的结果，即：SG(x)=Mex({SG(y_1),SG(y_2)\dots SG(y_k)})，特别地，整个有向图游戏G的SG函数值被定义为有向图游戏起点s的SG函数值，即 SG(G)=SG(s)
- SG函数的性质： 定义终点的SG函数值为0， SG(i)=k,k\ne 0，则i最大能到达的点的SG的范围为[0,k−1) 若SG(i)=0，说明走不到0
- 有向图游戏的和：若一个游戏的每个局面都可以构成一个有向图，则对于每个有向图的SG(G_1),SG(G_2)\dots SG(G_n)，对所有图的SG进行异或运算，即可得到该有向图游戏的和，且其结果满足Nim游戏
SG函数图解
- 根据每一步的不同选择生成路径单一的有向图，每条不同的路径对应不同的局面（方案）
- 定义终点的SG函数值为0，倒推起点的SG函数值
- 设一堆石子有10个，每次操作可取的数量为S={2,5}，无法操作即为终点，其SG函数如下：
证明有向图游戏的和符合Nim游戏
- 操作到最后时，每一种局面的SG(G_i)值都是0，即：0\oplus 0\oplus\dots\oplus0=0
- 在操作过程中，如果SG(G_1)\oplus SG(G_2)\oplus\dots\oplus SG(G_n)=x\ne 0，由SG函数的性质可知，玩家必然可以走到某一局面将异或结果变为0 \begin{aligned} 证明：&\\ &设x的二进制表示中最高一位1在第k位\\ &则SG(G_1),SG(G_2),\dots,SG(G_n)中，必然有一个局面SG(G_i)，其值的第k为1\\ &且一定满足:SG(G_i)\oplus x\lt SG(G_i)\\ &若将第i个局面的SG值取到(SG(G_i)\oplus x)\\ &由：SG(G_1)\oplus SG(G_2)\oplus\dots\oplus SG(G_i) \oplus\dots SG(G_n)=x\ne 0可知\\ &此时：SG(G_1)\oplus SG(G_2)\oplus\dots\oplus SG(G_i)\oplus x \oplus\dots SG(G_n)=x\oplus x=0 \end{aligned}
- 在操作过程中，如果SG(G_1)\oplus SG(G_2)\oplus\dots\oplus SG(G_n)=x=0，那么无论玩家如何更改局面，必然会导致最终异或结果不为0 \begin{aligned} 反证明：&\\ &假设玩家改变第i个局面的SG值，结果仍是0\\ &不妨设SG(G_i)改变后的值为SG(G_i)'，且SG(G_i)'\lt SG(G_i)\\ &此时仍有：SG(G_1)\oplus SG(G_2)\oplus\dots\oplus SG(G_i)'\oplus\dots SG(G_n)=0\\ &则有(SG(G_1)\oplus SG(G_2)\oplus\dots\oplus SG(G_i)'\oplus\dots SG(G_n))\\&=(SG(G_1)\oplus SG(G_2)\oplus\dots\oplus SG(G_i)\oplus\dots SG(G_n))=SG(G_i)'\oplus SG(G_i)=0\\ &即：SG(G_i)'=SG(G_i)，与原假设SG(G_i)'\lt SG(G_i)矛盾\\ &故假设不成立 \end{aligned}
- 综上：若先手面对的局面是SG(G_1)\oplus SG(G_2)\oplus\dots\oplus SG(G_n)=x\ne 0，则先手必胜，反之先手必败，符合Nim游戏
模板例题 893. 集合-Nim游戏
描述
给定 n 堆石子以及一个由 k 个不同正整数构成的数字集合 S。
现在有两位玩家轮流操作，每次操作可以从任意一堆石子中拿取石子，每次拿取的石子数量必须包含于集合 S，最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。
输入格式 第一行包含整数 k，表示数字集合 S 中数字的个数。
第二行包含 k 个整数，其中第 i 个整数表示数字集合 S 中的第 i 个数 si。
第三行包含整数 n。
第四行包含 n 个整数，其中第 i 个整数表示第 i 堆石子的数量 hi。
输出格式
如果先手方必胜，则输出 Yes。
否则，输出 No。
数据范围 1≤n,k≤100, 1≤si,hi≤10000 输入样例：
2
2 5
3
2 4 7输出样例：
Yes代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+3;
int n,m;
int s[N],f[N]; //s存储的是可供选择的集合,f存储的是所有可能出现过的情况的sg值
int sg(int x){
if(f[x]!=-1) return f[x]; //如果存储过了,直接返回
set<int> vis; //vis代表的是当前存在的数的集合
for(int i=0;i<m;i++){
int sum=s[i];
if(x>=sum) vis.insert(sg(x-sum)); //先得到到终点的sg值后,再从后往前倒推出所有数的sg值
}
for(int i=0;;i++){
if(!vis.count(i)) return f[x]=i; //Mex操作
}
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); //Nim游戏
}
if(res) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
}4.10.4 拆分-Nim 游戏
描述
给定 n 堆石子，两位玩家轮流操作，每次操作可以取走其中的一堆石子，然后放入两堆规模更小的石子（新堆规模可以为 0，且两个新堆的石子总数可以大于取走的那堆石子数），最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。
输入格式 第一行包含整数 n。
第二行包含 n 个整数，其中第 i 个整数表示第 i 堆石子的数量 ai。
输出格式
如果先手方必胜，则输出 Yes。
否则，输出 No。
数据范围 1≤n,ai≤100
输出样例：
2
2 3输出样例：
Yes分析
- 相比于
集合-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])
代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+3;
int n;
int f[N];
set<int> vis;
int sg(int x){
if(f[x]!=-1) return f[x];
for(int i=0;i<x;i++){
for(int j=0;j<=i;j++){ //规定j不大于i，避免重复
vis.insert(sg(i)^sg(j)); //相当于一个局面拆分成了两个局面
}
}
for(int i=0;;i++){
if(!vis.count(i)) return f[x]=i;
}
}
int main(){
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) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-7-12 1，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
