Chapter 4 数学知识
1：数论
质数（素数）
范围：从2开始的整数
定义：在大于1的整数中，只包含1和本身这两个约数
【1】质数的判定——试除法
bool is_prime(int x){if(n<2) return 0;for(int i=2;i<n;i++){if(n%i==0){return 0;}}return 1;
}
时间复杂度：O(n)
优化！！
n的所有约数都是成对出现，只用枚举每对中较小的那个
d <= n/d
d <= sqrt(n)
bool is_prime(int x){if(n<2) return 0;for(int i=2;i<=n/i;i++){if(n%i==0){return 0;}}return 1;
}
时间复杂度：O(sqrt(n))
不推荐写法：
i<=sqrt(n)
每一次都要求根号，调用函数比较慢
i*i<=n
当n接近于int最大值的时候，i*i容易溢出变成负数
【2】分解质因数——试除法
从小到大枚举所有数
重要定理：n中最多只包含一个大于sqrt(n)的质因子
void divide(int n){for(int i=2;i<=n/i;i++){//如果n可以整除iif(n%i==0){//计算可以分离出多少个iint s=0;while(n%i==0){n/=i;s++;}cout<<i<<s;}}if(n>1) cout<<n<<1;
}
时间复杂度：最差O(sqrt(n))，最好O(logn)
【3】筛质数——埃氏筛法
void get_primes(int n){//枚举for(int i=2;i<=n;i++){//如果没访问过if(!st[i]){//记为质数primes[cnt++]=i;}//把i的所有倍数全部删掉for(int j=i+1;j<=n;j+=i){st[j]=1;}}
}
时间复杂度：O(nloglogn)
优化！！——线性筛法
当i不是质数时，就不用删掉i的所有倍数，只需要删掉质数的所有倍数
质数定理：1到n中，有n/lnn个质数
保证每个合数是被自己的最小质因子筛掉的
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[prime[j]*i]=1;if(i%primes[j]==0){break;}}}
}
约数
【1】试除法求一个数的所有约数
# include <iostream>
# include <string.h>
# include <algorithm>
# include <stdio.h>
# include <vector>
# include <queue>
using namespace std;vector<int> get_divisors(int n){vector<int> res;for(int i=1;i<=n/i;i++){if(n%i==0){res.push_back(i);if(i!=n/i){res.push_back(n/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 t: res){cout<<t<<" ";}cout<<endl;}return 0;
}
/*
2
6
81 2 3 6
1 2 4 8
*/
【2】约数个数
N = p 1 a 1 ∗ p 2 a 2 ∗ . . . ∗ p k a k N=p_1^{a_1}*p_2^{a_2}*...*p_k^{a_k} N=p1a1∗p2a2∗...∗pkak
C o u n t = ( a 1 + 1 ) ∗ ( a 2 + 1 ) ∗ . . . ∗ ( a k + 1 ) Count =(a_1+1)*(a_2+1)*...*(a_k+1) Count=(a1+1)∗(a2+1)∗...∗(ak+1)
# include <iostream>
# include <string.h>
# include <algorithm>
# include <stdio.h>
# include <vector>
# include <queue>
# include <unordered_map>
using namespace std;typedef long long LL;
const int 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 prime:primes){res*=(prime.second+1)%mod;}cout<<res;return 0;
}
/*
3
2
6
812
*/
【3】约数之和
N = p 1 a 1 ∗ p 2 a 2 ∗ . . . ∗ p k a k N=p_1^{a_1}*p_2^{a_2}*...*p_k^{a_k} N=p1a1∗p2a2∗...∗pkak
S u m = ( p 1 0 + p 1 1 + . . . + p 1 a 1 ) ∗ . . . ∗ ( p k 0 + p k 1 + . . . + p k a k ) Sum=(p_1^{0}+p_1^{1}+...+p_1^{a^1})*...*(p_k^{0}+p_k^{1}+...+p_k^{a^k}) Sum=(p10+p11+...+p1a1)∗...∗(pk0+pk1+...+pkak)
乘法分配律展开，可得每一个约数
# include <iostream>
# include <string.h>
# include <algorithm>
# include <stdio.h>
# include <vector>
# include <queue>
# include <unordered_map>
using namespace std;typedef long long LL;
const int 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 prime:primes){int p=prime.first, a=prime.second;LL t=1;while(a--){t=(t*p+1)%mod;// 刚开始是p+1=t// 再来一次是(p+1)*p+1=p^2+p+1=t// 再来一次是(p^2+p+1)*p+1=p^3+p^2+p+1=t}res*=t%mod;}cout<<res;return 0;
}
/*
3
2
6
8252
*/
若d%a==0且d%b==0，则d%(ax+by)==0
所以，a和b的最大公约数 等于 b和(a%b)的最大公约数
# include <iostream>
# include <string.h>
# include <algorithm>
# include <stdio.h>
# include <vector>
# include <queue>
# include <unordered_map>
using namespace std;int gcd(int a,int b){return b ? gcd(b,a%b) : a;
} int main(){int n;cin>>n;while(n--){int a,b;cin>>a>>b;cout<<gcd(a,b)<<endl;}return 0;
}
/*
2
3 6
4 63
2
*/
时间复杂度O(logn)
欧拉函数
fai(n)：1~n中与n互质的数的个数
例如，n=6时，1、5和6互质，2、3、4不和6互质
因此，fai(6)=2
N = p 1 a 1 ∗ p 2 a 2 ∗ . . . ∗ p k a k N=p_1^{a_1}*p_2^{a_2}*...*p_k^{a_k} N=p1a1∗p2a2∗...∗pkak
f a i ( N ) = N ∗ ( 1 − 1 / p 1 ) ∗ . . . ∗ ( 1 − 1 / p n ) fai(N)=N*(1-1/p_1)*...*(1-1/p_n) fai(N)=N∗(1−1/p1)∗...∗(1−1/pn)
例如，N=6时，N=2x3
因此，fai(6)=6x(1-1/2)x(1-1/3)=2
核心：容斥原理
【1】欧拉函数
# include <iostream>
# include <string.h>
# include <algorithm>
# include <stdio.h>
# include <vector>
# include <queue>
# include <unordered_map>
using namespace std;int main(){int n;cin>>n;while(n--){int a;cin>>a;int res = a;//分解质因子for(int i=2;i<=a/i;i++){//如果i是a的质因子if(a%i==0){//fai(a)=fai(a)*(1-1/i)=fai(a)*(i-1)/ires=res/i*(i-1);//把这个因子除干净while(a%i==0) a/=i; }}//如果a有一个超大质因子if(a>1){res=res/a*(a-1);}cout<<res<<endl;}return 0;
}
/*
3
3
6
82
2
4
*/
【2】筛法求欧拉函数
求1~N中，每个数的欧拉函数，时间复杂度为n*sqrt(n)
# include <iostream>
# include <string.h>
# include <algorithm>
# include <stdio.h>
# include <vector>
# include <queue>
# include <unordered_map>
using namespace std;const int N=1e5+10;int primes[N],cnt;
int phi[N];
//fai(n)
bool st[N];typedef long long LL;//在线性筛法的过程中，求解欧拉函数
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;}for(int j=0;primes[j]<=n/i;i++){st[primes[j]*i]=1;if(i%primes[j] == 0){phi[primes[j]*i]=phi[i]*primes[j];break;}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);return 0;
}
/*
612
*/
euler定理
若 a 与 n 互质，则 a f a i ( n ) = 1 ( m o d ( n ) ) 若a与n互质，则a^{fai(n)}=1(mod(n)) 若a与n互质，则afai(n)=1(mod(n))
费马定理
若 a 和 p 互质，且 p 是质数，则 a p − 1 = 1 ( m o d ( p ) ) 若a和p互质，且p是质数，则a^{p-1}=1(mod(p)) 若a和p互质，且p是质数，则ap−1=1(mod(p))
快速幂
快速求出a^k mod p
时间复杂度O(log k)
核心思路：反复平方法
a k = a 2 x 1 ∗ a 2 x 2 ∗ . . . ∗ a 2 x t = a 2 x 1 + 2 x 2 + . . . + 2 x t a^k=a^{2^{x_1}}*a^{2^{x_2}}*...*a^{2^{x_t}}=a^{2^{x_1}+2^{x_2}+...+2^{x_t}} ak=a2x1∗a2x2∗...∗a2xt=a2x1+2x2+...+2xt
因此可以转换成 l o g k 次对 p 取模 因此可以转换成logk次对p取模 因此可以转换成logk次对p取模
第一次为： a 2 0 m o d ( p ) ，第二次为： a 2 1 m o d ( p ) ，第 l o g k 次为： a 2 l o g k m o d ( p ) 第一次为：a^{2^0}mod(p)，第二次为：a^{2^1}mod(p)，第logk次为：a^{2^{logk}}mod(p) 第一次为：a20mod(p)，第二次为：a21mod(p)，第logk次为：a2logkmod(p)
同时， a 2 l o g k = ( a 2 l o g k − 1 ) 2 同时，a^{2^{logk}}=(a^{2^{logk-1}})^2 同时，a2logk=(a2logk−1)2
# include <iostream>
# include <string.h>
# include <algorithm>
# include <stdio.h>
# include <vector>
# include <queue>
# include <unordered_map>
using namespace std;typedef long long LL;//a^k % p
int qmi(int a, int k, int p){int res=1;while(k){//k的二进制个位是1 if(k & 1){res=(LL) res*a%p;}//右移一位 k >>= 1;a = (LL) a*a%p;}return res;
}int main(){int n;cin>>n;while(n--){int a,k,p;cin>>a>>k>>p;cout<<qmi(a,k,p);}return 0;
}
/*
2
3 2 5
4 3 94
1
*/
题目：快速幂求逆元
a / b = a ∗ x ( m o d ( m ) ) a/b =a*x(mod(m)) a/b=a∗x(mod(m))
将a/b，变成a(b的逆元)*
b存在逆元的充要条件：b与模数m互质
当模数m为质数时，b^(m-2)是b的乘法逆元
# include <iostream>
# include <string.h>
# include <algorithm>
# include <stdio.h>
# include <vector>
# include <queue>
# include <unordered_map>
using namespace std;typedef long long LL;//a^k % p
int qmi(int a, int k, int p){int res=1;while(k){//k的二进制个位是1 if(k & 1){res=(LL) res*a%p;}//右移一位 k >>= 1;a = (LL) a*a%p;}return res;
}int main(){int n;cin>>n;while(n--){int a,p;cin>>a>>p;int res=qmi(a,p-2,p);if(a%p)cout<<res;elseputs("impossible");}return 0;
}
/*
3
4 3
8 5
6 31
2
impossible
*/
扩展欧几里得
裴蜀定理
对于任意正整数a和b，一定存在非0整数x和y，使得ax+by=gcd(a,b)
扩展欧几里得：求解整数x和y
基本欧几里得为：(a,b) = (b, a mod b)
令d是gcd(a,b)
根据裴蜀定理可得：by + (a mod b)x = d
取余可化简为：a mod b = a - [a/b] b
化简结果为：ax + b(y - [a/b] x) = d
因此，x不需要更新，而y需要更新
# include <iostream>
# include <string.h>
# include <algorithm>
# include <stdio.h>
# include <vector>
# include <queue>
# include <unordered_map>
using namespace std;typedef long long LL;int exgcd(int a,int b,int &x,int &y){if(b==0){x=1;y=0;return a;}int d=exgcd(b, a%b, y, x);y -= a/b*x;return d;
}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;
}
/*
2
4 6
8 18-1 1
-2 1
*/
题目：线性同余方程
# include <iostream>
# include <string.h>
# include <algorithm>
# include <stdio.h>
# include <vector>
# include <queue>
# include <unordered_map>
using namespace std;typedef long long LL;int exgcd(int a,int b,int &x,int &y){if(b==0){x=1;y=0;return a;}int d=exgcd(b, a%b, y, x);y -= a/b*x;return d;
}int main(){int n;cin>>n;while(n--){int a,b,m;cin>>a>>b>>m;int x,y;int d=exgcd(a,m,x,y);if(b%d) puts("impossible");else cout<<(LL)x*(b/d)%m;}return 0;
}
/*
2
2 3 6
4 3 5impossible
-3
*/
2：组合计数
求组合数的定义：
C a b = a ! b ! ( a − b ) ! C_a^b=\frac{a!}{b!(a-b)!} Cab=b!(a−b)!a!
递推求组合数的公式：
C a b = C a − 1 b + C a − 1 b − 1 C_a^b=C_{a-1}^b+C_{a-1}^{b-1} Cab=Ca−1b+Ca−1b−1
求组合数1：递推
10万组，a和b属于1~2000
# include <iostream>
# include <string.h>
# include <algorithm>
# include <stdio.h>
# include <vector>
# include <queue>
# include <unordered_map>
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;}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];}return 0;
}
/*
3
3 1
5 3
2 23
10
1
*/
求组合数2：预处理阶乘
1万组，a和b属于1~100000
阶乘的打表：
f a c t [ i ] = ( i ! ) m o d ( 1 e 9 + 7 ) fact[i]=(i!)mod(1e9+7) fact[i]=(i!)mod(1e9+7)
逆阶乘的打表：
i n f a c t [ i ] = ( i ! ) − 1 m o d ( 1 e 9 + 7 ) infact[i]=(i!)^{-1}mod(1e9+7) infact[i]=(i!)−1mod(1e9+7)
根据组合数的定义，可得：
C a b = f a c t [ a ] ∗ i n f a c t [ b − a ] ∗ i n f a c t [ b ] C_a^b=fact[a]*infact[b-a]*infact[b] Cab=fact[a]∗infact[b−a]∗infact[b]
# include <iostream>
# include <string.h>
# include <algorithm>
# include <stdio.h>
# include <vector>
# include <queue>
# include <unordered_map>
using namespace std;typedef long long LL;const int N = 1e5+10,MOD = 1e9+7;
int fact[N],infact[N];int qmi(int a, int k, int p){int res=1;while(k){//k的二进制个位是1 if(k & 1){res=(LL) res*a%p;}//右移一位 k >>= 1;a = (LL) a*a%p;}return res;
}int main() {fact[0] = 1;infact[0] = 1;//对于每一个数字n进行计算for (int i = 1; i < N; i++) {fact[i] = (LL) fact[i - 1] * i % MOD; //强制转为LL是为了防止越界// 费马小定理求i逆元infact[i] = (LL) infact[i - 1] * qmi(i, MOD - 2, MOD) % MOD;}int n;cin >> n;while (n--) {int a, b;cin >> a >> b;//公式C(a,b)=a!/(b!*(a-b)!)printf("%d\n", (LL) fact[a] * infact[b] % MOD * infact[a - b] % MOD);}return 0;
}
/*
3
3 1
5 3
2 23
10
1
*/
求组合数3：Lucas定理
20组，a和b属于110^18，p属于110^5
Lucas定理
C a b = C ( a ) m o d ( p ) ( b ) m o d ( p ) ∗ C ( a ) / ( p ) ( b ) / ( p ) ( M O D p ) C_a^b=C_{(a)mod(p)}^{(b)mod(p)}*C_{(a)/(p)}^{(b)/(p)}(MODp) Cab=C(a)mod(p)(b)mod(p)∗C(a)/(p)(b)/(p)(MODp)
# include <iostream>
# include <string.h>
# include <algorithm>
# include <stdio.h>
# include <vector>
# include <queue>
# include <unordered_map>
using namespace std;typedef long long LL;int p;int qmi(int a, int k){int res=1;while(k){//k的二进制个位是1 if(k & 1){res=(LL) res*a%p;}//右移一位 k >>= 1;a = (LL) a*a%p;}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);return (LL)C(a%p,b%p)*lucas(a/p,b/p)%p;
}int main() {int n;cin>>n;while(n--){LL a,b;cin>>a>>b>>p;cout<<lucas(a,b)<<endl;}return 0;
}
/*
3
5 3 7
3 1 5
6 4 133
3
2
*/
求组合数4：高精度乘法和除法
计算公式：
C a b = a ∗ ( a − 1 ) ∗ . . . ∗ ( a − b + 1 ) b ∗ ( b − 1 ) ∗ . . . ∗ 1 C_a^b=\frac{a*(a-1)*...*(a-b+1)}{b*(b-1)*...*1} Cab=b∗(b−1)∗...∗1a∗(a−1)∗...∗(a−b+1)
核心思路：
【1】进行质因数分解
【2】写高精度乘法
# include <iostream>
# include <string.h>
# include <algorithm>
# include <stdio.h>
# include <vector>
# include <queue>
# include <unordered_map>
using namespace std;typedef long long LL;const int N=5010;
int primes[N],cnt,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]=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(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]);}}for(int i=res.size()-1;i>=0;i--){cout<<res[i];}puts("");return 0;
}
/*
5 310
*/
卡特兰数
0：向右走一个格子
1：向上走一个格子
公式递归计算
C 2 n n − C 2 n n − 1 = C 2 n n n + 1 C_{2n}^{n}-C_{2n}^{n-1}=\frac{C_{2n}^{n}}{n+1} C2nn−C2nn−1=n+1C2nn
题目：满足条件的01序列
# include <iostream>
# include <string.h>
# include <algorithm>
# include <stdio.h>
# include <vector>
# include <queue>
# include <unordered_map>
using namespace std;typedef long long LL;const int 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=2*n,b=n,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;return 0;
}
/*
5 310
*/
3：高斯消元
作用：求解多元线性的方程组
解的情况：
【1】无解
【2】无穷多组解
【3】唯一解
输入n*(n+1)的系数矩阵
矩阵的初等行列变换
【1】把某行的系数乘以一个非0数
【2】交换某2行
【3】把某行的若干倍，加到另一行上
通过初等变换，把矩阵变成上三角形式
【1】完美阶梯形——唯一解
【2】有行出现：0=非零——无解
【3】有行出现：0=0——无穷多组解
高斯消元步骤
【0】枚举每一列c
【1】找到当前列c中绝对值最大的一行
【2】将该行换到最上面
【3】将该行的第一个数变成1
【4】将下面所有行的当前列c清0
# include <iostream>
# include <string.h>
# include <algorithm>
# include <stdio.h>
# include <vector>
# include <queue>
# include <unordered_map>
using namespace std;const int N = 110;
int n;
double a[N][N];
const double eps=1e-8;int gauss() { // 高斯消元，答案存于a[i][n]中，0 <= i < nint r = 0; // 先按行后按列进行计算，当前行是第1行for (int c = 0; c < n; c++) { // 枚举每一列int t = r; // 防破坏r,复制出tfor (int i = r; i < n; i++) // 当前行需要找它的后续行if (abs(a[i][c]) > abs(a[t][c])) t = i; // t的任务是找出c列中系数最大值是哪一行if (abs(a[t][c]) < eps) continue; // 如果c列绝对值最大的系数是0, 那么处理下一列for (int i = c; i <= n; i++) swap(a[t][i], a[r][i]); // 将绝对值最大的行与当前行交换for (int i = n; i >= c; i--) a[r][i] /= a[r][c]; // a[r][c]:行首系数，将当前行的行首通过除法变为1,倒序for (int i = r + 1; i < n; i++) // 用当前行r的c列，通过减法将后续行c列消成0for (int j = n; j >= c; j--) // 倒序,需要保留行首，逻辑和上面是一样的，行首值是变更系数，如果正序就把系数变成1了，后面就不对了a[i][j] -= a[r][j] * a[i][c]; // a[i][c]:需要变化的乘法系数，减法：对位相消r++; // 下一行}if (r < n) { // 如果没有成功执行完所有行，意味着中间存在continue,也就是某一列的系数都是0for (int i = r; i < n; i++)if (abs(a[i][n]) > eps) return 0; // 系数是0，但结果不是0，无解return 2; // 系数是0，结果也是0，x取啥都对，有无穷多组解}// 代回求每个变量值for (int i = n - 2; i >= 0; i--) // 行,倒序for (int j = i + 1; j < n; j++) // 列,倒三角,右上角应该都是0,对角线全是1a[i][n] -= a[i][j] * a[j][n]; // 系数消为0return 1; // 有唯一解
}int main() {cin >> n;for (int i = 0; i < n; i++) // n个方程for (int j = 0; j <= n; j++) // 每行n+1个数据，因为最后一列是等号右侧值cin >> a[i][j];int t = gauss();if (t == 0)puts("No solution");else if (t == 2)puts("Infinite group solutions");elsefor (int i = 0; i < n; i++) printf("%.2lf\n", a[i][n]); // 保留两位小数return 0;
}
/*
3
1.00 2.00 -1.00 -6.00
2.00 1.00 -3.00 -9.00
-1.00 -1.00 2.00 7.001.00
-2.00
3.00
*/
4：容斥原理
C n 0 + C n 1 + . . . + C n n = 2 n C_n^0+C_n^1+...+C_n^n=2^n Cn0+Cn1+...+Cnn=2n
含义：从n个数中选任意多个数的方案数
左侧：按组合数学排列
右侧：每个数有取和不取两个情况
容斥原理
所有元素交集的个数 = 奇数个元素交集之和 − 偶数个元素交集之和 所有元素交集的个数=奇数个元素交集之和 - 偶数个元素交集之和 所有元素交集的个数=奇数个元素交集之和−偶数个元素交集之和
题目：能被整除的数
给定一个整数 n 和 m 个不同的质数 p1,p2,…,pm。
请你求出 1∼n 中能被 p1,p2,…,pm 中的 至少一个数整除的整数 有多少个。
# include <iostream>
# include <string.h>
# include <algorithm>
# include <stdio.h>
# include <vector>
# include <queue>
# include <unordered_map>
using namespace std;typedef long long LL;const int N=20;int n,m;
int p[N];int main() {cin>>n>>m;//读入m个质数for(int i=0;i<m;i++){cin>>p[i];}int res=0; //表示答案//从1枚举到2^m，即00...01枚举到11...11for(int i=1;i<1<<m;i++){int t=1,cnt=0; //t表示当前所有质数的乘积，cnt表示当前选法里面有几个集合for(int j=0;j<m;j++){if(i>>j &1){//如果当前这一位是1cnt++;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;return 0;
}
/*
10 2
2 37
*/
5：简单博弈论
题目：Nim游戏
先手必胜状态：可以走到某一个对手必败状态
先手必败状态：走不到任何一个对手必败状态
有 a 1 , a 2 , . . . , a n ，若 a 1 异或 a 2 异或 . . . 异或 a n = 0 ，则先手必败，否则先手必胜 有a_1,a_2,...,a_n，若a_1异或a_2异或...异或a_n=0，则先手必败，否则先手必胜 有a1,a2,...,an，若a1异或a2异或...异或an=0，则先手必败，否则先手必胜
# include <iostream>
# include <string.h>
# include <algorithm>
# include <stdio.h>
# include <vector>
# include <queue>
# include <unordered_map>
using namespace std;int main() {int n,res=0;cin>>n;while(n--){int x;cin>>x;res ^= x;//异或}if(res){puts("Yes");}else{puts("No");}return 0;
}
/*
2
2 3Yes
*/
题目：集合Nim游戏
# include <iostream>
# include <string.h>
# include <algorithm>
# include <stdio.h>
# include <vector>
# include <queue>
# include <unordered_set>
using namespace std;const int N=110, M=10010;int n,m;
int s[N],f[M];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));}}for(int i=0;;i++){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;
}
/*
2
2 5
3
2 4 7Yes*/
