主要内容
- 质数：判定、分解、线性筛
- 组合计数、高斯消元、简单博弈论

算术基本定理：

$N=P_{1}^{a_{1}}· P_{2}^{a_{2}}...P_{k}^{a_{k}}$

任意数字N都能分解成上面的这些形式，且Pi都是不同的质数，且a都大于0；

所以N能分解成a1+a2+..ak个质因子

质数

定义（素数/质数）：在大于1 的整数中，如果只包含1和本身这两个约数

质数判定-试除法 O(√n)

bool is_prime(int n){
	if(n<2) return false;
    for(int i=2;i<=n/i;i++) //注意有等号，不建议写成i*i<=n
		if(n%i==0) return false;
    return true;
}

分解质因数-试除法 O(√n)

从小到大枚举所有数，

void divide(int x){
	//x中最多只有一个大于sqrt(x)的质因子 
	for(int i=2;i<=x/i;i++){
		//如果i是x的因数 
		if(x%i==0){
			int s=0;//i的个数
			//x将i的因子除尽，下一轮的x的因子就不包含i 
			while(x%i==0) x/=i,s++;
			cout<<i<<' '<<s<<endl;
		} 
	}
	if(x>1) cout<<x<<' '<<1<<endl;
	//cout<<endl;
}

线性筛求质数O(n)

get_primes(int n)：求出1到n的所有质数

质数定理：1到n当中有n/lnn个质数

朴素做法 时间复杂度 O(nlogn)

遍历从2到n的数，如果没被筛过，说明是质数，存到primes里；
对于该质数，往后遍历所有它的倍数，它的倍数一定是合数，标记为筛过。

int primes[N],cnt; //prime[]存储1到n的所有质数，cnt所有质数的个数
bool st[N];        //st[i]：数字是否被筛过 
void get_primes(int n){
	for(int i=2;i<=n;i++){
		if(!st[i]) primes[cnt++]=i;
		for(int j=i+i;j<=n;j+=i) st[j]=true;
	}
}

优化做法一：埃氏筛法：时间复杂度O(nloglogn)

对于该质数，我们不需要把后面的每个它的倍数都筛掉，只需要筛掉质数的倍数就行

比如对于 2 3 4 5 6 7 8 9 10 11,

筛掉后是2 3 4 5 6 7 8 9 10 11

比如筛剩下质数p = 11，对于2到p-1中的数，并不需要全部判断一下，只需要把其中的质数判断一下就可以了。
只要2到p-1的质数不是p的因数的话，那么p就是一个质数
所以筛的话，只需要筛掉质数的倍数就可以了 (因为合数一定是质数的倍数)

int primes[N],cnt; //prime[]存储1到n的所有质数，cnt所有质数的个数
bool st[N];        //st[i]：数字是否被筛过 
void get_primes(int n){
	for(int i=2;i<=n;i++){
		if(!st[i]){
			primes[cnt++]=i;
            for(int j=i+i;j<=n;j+=i) st[j]=true;
        } 	
	}
}

优化做法二：线性筛法：时间复杂度O(n)

核心：把每个数只会被它的最小质因子筛掉

i%primes[j] == 0：
- primes[j] 一定是 i 的最小质因子，primes[j] 一定是 primes[j] * i 的最小质因子
i%primes[j] != 0：
- 。。。。

int primes[N],cnt; //prime[]存储1到n的所有质数，cnt所有质数的个数
bool st[N];        //st[i]：数字是否被筛过 
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++){
            //把当前质数(最小质因子）和i（最大因数）的乘积筛掉
			int t=primes[j]*i;
			st[primes[j]*i]=true;
			if(i%primes[j]==0) break;//此时 primes[j]一定是i的最小质因子
		}
	}
}

AcWing1292哥德巴赫猜想

验证小于一百万的偶数是否满足哥德巴赫猜想：

任意一个大于4的偶数都能拆成两个奇素数之和。

对于每个数据，输出奇素数差值最大的一组

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int primes[N],cnt;
bool st[N];
void get_primes(int x){
	for(int i=2;i<=x;i++){
		if(!st[i]) primes[cnt++]=i;
		for(int j=0;primes[j]*i<=x;j++){
			int t=i*primes[j];
			st[t]=true;
			if(i%primes[j]==0) break;
		}
	}
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	get_primes(N);//先找到100万以内的素数，
	while(1){
		int x; cin>>x;
		if(x==0) return 0;
		for(int i=0;i<cnt;i++){
			if(!st[x-primes[i]]){
					cout<<x<<" = "<<primes[i]<<" + "<<x-primes[i]<<endl;
					break;
			}
		}
	}
}

约数

试除法求约数 O(sqrt(n))

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;
}

约数个数

基于算术基本定理，约数个数=（α1+1)*(α2+1）…（αk+1）

int范围内约数最多的一个整数的约数大概一千五六百的样子

模板题

求给定N个数的乘积 的约数的个数

先分解质因数成算术基本定理的形式（分别分解每一个）

#include<bits/stdc++.h>
#include<unordered_map>//哈希表 
using namespace std;
typedef long long LL;
const int mod=1e9+7;
int main(){
	int n;cin>>n;
	//定义一个哈希表存储所有的底数和指数
	//第一个int：primes[i]中的i：底数 
	//第二个int：primes[i]存放的值：指数 
	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=res*(prime.second+1)%mod;
	}
	cout<<res<<endl;
	return 0;	
}

约数之和

基于算术基本定理，一个数的所有约数的和

$(P_{1}^{0}+P_{1}^{1}+P_{1}^{2}+...+P_{1}^{α1})*...*(P_{k}^{0}+P_{k}^{1}+P_{k}^{2}+...+P_{k}^{αk})$

模板题

求N个数的乘积的约数之和，答案对1e9+7取模

#include<bits/stdc++.h>
#include<unordered_map>//哈希表 
using namespace std;
typedef long long LL;
const int mod=1e9+7;
int main(){
	int n;cin>>n;
	//定义一个哈希表存储所有的底数和指数
	//第一个int：primes[i]中的i：底数 
	//第二个int：primes[i]存放的值：指数 
	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,k=1;
		while(a--){
			k=(k*p)%mod;t=(t+k)%mod;
		}
	//	while(a--) t=(t*p+1)%mod ;
		res=res*t%mod;
	}
	cout<<res<<endl;
	return 0;	
}

最大公约数（欧几里得算法）

(辗转相除法)：如果d能整除a，d能整除b，那么d就能整除a+b

a和b的最大公约数 = b和a mod b的最大公约数

int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}
//STL里有： __gcd(int a,int b); 注意前面是两个下划线

欧拉函数

1到N中和N 互质的数的个数

$Φ(N)=N(1-\frac{1}{P_{1}})(1-\frac{1}{P_{2}})...(1-\frac{1}{P_{k}})$

容斥原理

$|S_{1}\cup S_{2}\cup S_{3}|=|S_{1}|+|S_{2}|+|S_{3}|-|S_{1}\cap S_{2}|-|S_{1}\cap S_{3}|-|S_{2}\cap S_{3}|+|S_{1}\cap S_{2}\cap S_{3}|$

依次类推

简单博弈论

其他题

求最大公约数，gcd(a,b)：欧几里得算法（辗转相除法）logn

gcd (a,b) = gcd (b,a mod b)

1
2
3

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

AcWing1246 等差数列

所有相邻的两个数的公差必然是2的倍数，即找公差的最大公约数

0和任何数的最大公约数就是那个任何数

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N];
int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}
int main(){
	ios::sync_with_stdio(false);
	int n;cin>>n;
	for(int i=0;i<n;i++)cin>>a[i];
	sort(a,a+n);
	int d=0;
	for(int i=1;i<n;i++) d=gcd(d,a[i]-a[i-1]);
	if(!d) cout<<n<<endl;
	else cout<<(a[n-1]-a[0])/d+1<<endl;
}

线性筛求素数：在On的复杂度内求出1-n的所有质数以及每个数的最小质因子

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;

int primes[N],cnt;//存所有的质数，cnt表示个数
bool st[N];//当前这个数有没有被筛过 

//线性筛 O(n) 
//对于每一个数（无论质数合数）x，筛掉所有小于x最小质因子的质数乘以x的数。
//比如对于77,它分解质因数是7*11，那么筛掉所有小于7的质数*77，筛掉2*77、3*77、5*77。 
int get_primes(int n){
	for(int i=2;i<=n;i++){
		//如果当前数没有被筛过的话就说明是个质因子 
		if(!st[i]) primes[cnt++]=i;
		//从小到大枚举所有的质数，把这个质数的i倍筛掉 
		for(int j=0;primes[j]*i<=n;j++){
			st[primes[j]*i]=true; //筛掉的一定是合数 
			if(i%primes[j]==0) break;
 		}
	}
} 

int main(){
	ios::sync_with_stdio(false),cin.tie(0);

	get_primes(1000);
	for(int i=0;i<20;i++) cout<<primes[i]<<endl;;
}

AcWing1295

题意

输入正整数 X，求 X的大于 1 的因子组成的满足任意前一项都能整除后一项的严格递增序列的最大长度，以及满足最大长度的序列的个数。

思路

代码

LiaN

【题解】数学知识

质数