一、斐波那契数列

注意90项大概就会超出int范围
如果项数太大取模的话，可以参考之前的做法。

如果给你一个数列：a(1) = 1， a(n+1) = 1 + 1/a(n)。
那么它的通项公式为：a(n) = fib(n+1) / fib(n)。

#include<bits/stdc++.h>

using namespace std;

int f[10005] = {0};
int main(){
	int n;
	cin >> n;
	f[0] = 1, f[1] = 1;
	for(int i = 2; i <= n; ++i){
		f[i] = f[i-1] + f[i-2];
		f[i] = f[i] % 2333333;
	}
	cout << f[n] << endl;
	return 0;
}

二、素数判定

注意两点：首先，小于2的数都不是素数。其次，只用判断到根号n即可。

#include<bits/stdc++.h>

using namespace std;

bool sushu(int n){
	bool flag = 0;
	if(n == 1) return 0; //1不是素数 
	else{
		for(int i = 2; i <= sqrt(n); ++i){
			if(n % i == 0) return 0; 
		}
		return 1;
	}
}
int main(){
	int n;
	cin >> n;
	for(int i = n; ;++i){
		if(sushu(i) == 1){
			cout << i << endl;
			break;
		}
	}
	return 0;
}

三、素数筛选

用以上方法挨个判断，只能处理10000以内的数。
如下方法是线性复杂度

#include<bits/stdc++.h>

using namespace std;

//线性素数筛选，prime[0]是素数个数

const int maxn = 1000000 + 5;
int prime[maxn];
void getPrime() {  
    memset(prime, 0, sizeof(prime));  
    for (int  i = 2; i <= maxn; i++) {  
        if (!prime[i]) prime[++prime[0]] = i;  
        for (int j = 1; j <= prime[0] && prime[j] * i <= maxn; j++) {  
            prime[prime[j] * i] = 1;  
            if (i % prime[j] == 0) break;  
        }  
    }  
}  

int main(){
	getPrime();
	int a, b;
	while(cin >> a >> b){
		if(a > b) swap(a, b);
		int ans = 0;
		for(int i = 1; i <= prime[0]; ++i){
			if(prime[i] >= a && prime[i] < b){
				ans++;
			}
		}
		cout << ans << endl;
	}
	return 0;
}

四、分解素因数

前提：素因数的分解是唯一的！
1000000的素数完全够了，如果有两个素因子都大于1000000，那么这个数会大于1000000000000，超出int范围，所以数顶多只有一个超过1000000，那么只要最后当剩下一个大素因子时，把ans++即可。

#include<bits/stdc++.h>

using namespace std;

//线性素数筛选，prime[0]是素数个数,prime中其他元素是所有素数 

const int maxn = 1000000 + 5;
int prime[maxn];
void getPrime() {  
    memset(prime, 0, sizeof(prime));  
    for (int  i = 2; i <= maxn; i++) {  
        if (!prime[i]) prime[++prime[0]] = i;  
        for (int j = 1; j <= prime[0] && prime[j] * i <= maxn; j++) {  
            prime[prime[j] * i] = 1;  
            if (i % prime[j] == 0) break;  
        }  
    }  
}  

int main(){
	getPrime();
	int n;
	while(cin >> n){
		int ans = 0;
		for(int i = 1; i <= prime[0]; ++i){
			while(n % prime[i] == 0){
				n = n / prime[i];
				ans++;
			}
			if(n == 1) break;
		}
		if(n > 1) ans++; //对于大于1000000的素因子，不可能两个都大于，这样会超过范围 
		cout << ans << endl;
	} 
	return 0;
}

五、二分快速幂

有一类题目是这样的
求 (x^y) % p
当y很大的时候，我们不能直接用for去一个一个的乘，因为这样的方法复杂度是O(N)的。
可以把y分解，分解成1+2+4+8…这样翻倍。

#include<bits/stdc++.h>

using namespace std;

typedef long long int ll;

ll mod_pow(ll x, ll y, ll mod){
	ll res = 1;
	while(y > 0){
		//只有当该位为1时，去乘此时的x 
		if(y % 2 == 1) res = res * x % mod;
		x = x * x % mod;
		y = y / 2;
	}
	res = res % mod;
	return res;
}

int main(){
	ll x, n;
	cin >> x >> n;
	cout << mod_pow(x, n, 233333) << endl;
	return 0; 
}

如果x大，y也大，两步走，先大数取模，再二分快速幂。

六、常见数学公式总结

1 错排公式

问题： 十本不同的书放在书架上。现重新摆放，使每本书都不在原来放的位置。有几种摆法？
递推公式为：D(n) = (n - 1) * [D(n - 1) + D(n - 2)]
n=1时，0种；n=2时，1种；n=3时，2种。

2 海伦公式

S = sqrt(p * (p - a) * (p - b) * (p - c))
公式描述：公式中a，b，c分别为三角形三边长，p为半周长，S为三角形的面积。

3 组合数公式

公式描述：
组合数公式是指从n个不同元素中，任取m(m≤n)个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合。

4 卡特兰数

七、规律神器OEIS

http://oeis.org/