本人是刚学算法的萌新，还请大佬们指正。

这篇文章主要是介绍质数，约数，欧拉函数，快速幂，扩展欧几里得算法，中国剩余定理，高斯消元，求组合数，容斥原理，博弈论的相关内容。

现在还在完善ing，之后会补上一些例题

1.质数

1.1质数的判定（试除法） O(sqrt(n))

质数的定义：该数的因子只有1和本身。

输入一个数判断它是否是质数

bool isprime(int n){
	if(n<2) return false;
	for(int i=2;i<=n/i;i++){
		if(n%i==0) return false;
	}
	return true;
}

1.2分解质因数（试除法）  O(sqrt(n))

(其中a1~ak均为质数） 

题意：输入n，每行输出

思路：由于不存在一个数有两个>sqrt（n）的质因子（反证法：若n能分解成两个>sqrt（n）的质因子，则这两个质因子的乘积必然>n），所以只需枚举2~sqrt（n）判断该数的质因子，若i是n的质因子，则一直n/=i，直到n%i！=0次数就是。需要注意的是我们是枚举2~sqrt（n）如果n最后不等于1，那么n就是最后一个>sqrt（n）的质因子。代码如下：

void divide(int n) {
	for(int i=2; i<=n/i; i++) {
		if(n%i==0) { //这里i绝对为质数
			int s=0;
			while(n%i==0) {
				n/=i;
				s++;
			}
			printf("%d %d\n",i,s);
		}
	}
	if(n!=1) printf("%d %d\n",n,1);//可能存在一个>sqrt(n)的质因子 ；
}

1.3筛质数

1.3.1埃氏筛法      算法复杂度o（nloglogn）

求1~n里面的质数

思路：

把2的倍数筛了：4，6，8，10，12，14，16，18，20，22.....

把3的倍数筛了：6，9，12，15，18，21，24，27，30，33......

把4的倍数筛了：4，8，12，16，20，24，28，32，36，40.....

把5的倍数筛了：5，10，15，20，25，30，35，40，45，50.....

把6的倍数筛了：6，12，18，24，30，36，42，48，54，60.....

把7的倍数筛了...........

.........

那么没被筛过的数就是质数啦（2，3，5，7，11，13，15.....）

代码如下：

#include <iostream>
using namespace std;
const int N=1e6;
bool st[N];//是否被筛过 
int prime[N],cnt;
void get_prime(int n){
	for(int i=2;i<=n;i++){
		if(!st[i]){
			prime[cnt++]=i;			 
		}
		for(int j=i+i;j<=n;j+=i) st[j]=true; 
	}
	for(int i=0;i<cnt;i++) cout<<prime[i]<<endl;
}
int main(int argc, char** argv) {
	int n;
	cin>>n;
	get_prime(n);
	return 0;
}

但是仔细想想，能不能优化呢，比如我把2的倍数筛完了，我需不需要筛4的倍数呢，需不需要筛6的倍数呢，同样的道理我既然把3的倍数筛过了，需不需要筛6的倍数呢，还需不需要把9的倍数筛了呢，显然是不需要的。

所以我们只需要稍微变一下就行了，从而优化了算法。

代码如下：（唯一的区别在于for循环的位置）

#include <iostream>
using namespace std;
const int N=1e6;
bool st[N];//是否被筛过
int prime[N],cnt;
void get_prime(int n) {
	for(int i=2; i<=n; i++) {
		if(!st[i]) {
			prime[cnt++]=i;
			for(int j=i+i; j<=n; j+=i) st[j]=true;
		}

	}
	for(int i=0; i<cnt; i++) cout<<prime[i]<<endl;
}
int main(int argc, char** argv) {
	int n;
	cin>>n;
	get_prime(n);
	return 0;
}

1.3.2线性筛法     算法复杂度o（n）

这是我们需要掌握的，线性筛用处范围很广，很多算法都是由它扩展的。

首先要知道什么是线性：利用了每个合数必有一个最小素因子每个合数仅被它的最小素因子筛去正好一次。所以为线性时间。（关键）
代码中体现在：
if(i%prime[j]==0)break;（最需要理解的部分）
 

废话不多说，上代码：

#include <iostream>

using namespace std;
const int N=1e6;
int p[N],cnt=0;
bool st[N];
void get_prime(int n){
	for(int i=2;i<=n;i++){
		if(!st[i])	p[cnt++]=i;
			for(int j=0;p[j]<=n/i;j++){
				st[p[j]*i]=true;
				if(i%p[j]==0) break;
			}
	}
	for(int i=0;i<cnt;i++) cout<<p[i]<<endl;
}
int main(int argc, char** argv) {
	int n;
	cin>>n;
	get_prime(n);
	return 0;
}