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可以整除i
if(n%i==0){
//计算可以分离出多少个i
int 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
8
1 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
8
12
*/
【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
8
252
*/
【4】欧几里得算法（辗转相除）
若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 6
3
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)/i
res=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
8
2
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;
}
/*
6
12
*/
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 9
4
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;
else
puts("impossible");
}
return 0;
}
/*
3
4 3
8 5
6 3
1
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 5
impossible
-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 2
3
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 2
3
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 13
3
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 3
10
*/
卡特兰数
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 3
10
*/
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 < n
int r = 0; // 先按行后按列进行计算，当前行是第1行
for (int c = 0; c < n; c++) { // 枚举每一列
int t = r; // 防破坏r,复制出t
for (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列消成0
for (int j = n; j >= c; j--) // 倒序,需要保留行首，逻辑和上面是一样的，行首值是变更系数，如果正序就把系数变成1了，后面就不对了
a[i][j] -= a[r][j] * a[i][c]; // a[i][c]:需要变化的乘法系数，减法：对位相消
r++; // 下一行
}
if (r < n) { // 如果没有成功执行完所有行，意味着中间存在continue,也就是某一列的系数都是0
for (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,对角线全是1
a[i][n] -= a[i][j] * a[j][n]; // 系数消为0
return 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");
else
for (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.00
1.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...11
for(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){
//如果当前这一位是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;
return 0;
}
/*
10 2
2 3
7
*/
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 3
Yes
*/
题目：集合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 7
Yes
*/
