直接和数学相关的题可以非常高深，这里只有最简单最初步的一小部分。对应《算法竞赛入门经典（第二版）》第十章。

一点数论（和因数（约数）相关 ）#

最大公约数欧几里得法#

最大公约数GCD的欧几里得算法
$gcd(a,b)=gcd(b, a\%b), gcd(c,0)=1$

int gcd(int a, int b){  
	if(b==1) return 1;  
	return gcd(b, a%b);  
}  

ab初始大小无所谓，让a>b能少一层递归。欧几里得法的递归层数不超过 4.785lgN+1.6723。（最大的情况是两个相邻的斐波那契数，很神奇）。

最小公倍数
lcm(a,b)=a * b / gcd(a,b) 很好证。
编程应该先除后乘防止溢出。

给出一个数列，表示X1/X2/X3/X4…/Xn，问能否通过加括号，使得这个除法表达式结果为整数。

首先分母尽可能少，分子尽可能多。而X2是一定要在分母里，无论怎么加括号也不行（X2前面那个除号无论如何变不成乘号），而在X2后与Xn后加括号，可以把除了X2意外的全部翻到分子上，这是最有可能是整数的。
只用判断 X1X3X4X5X6…Xn/X2 是否是整数即可。
一种方法是对X2分解质因数，记录全部次数，然后尝试所有分子中能除掉几个质因数，判断是否除尽。或者直接对所有分子分解质因数，记录每个质因数次数的总和，然后和分母比较大小。但是分解质因数会比较麻烦。
还有就是挨个约分。

for(int i=0;i<n;i++){  
	if(i==1) continue;  
	X[1] /= gcd(X[1], X[i]);  
	if(X[1]==1) return true;  
}  
return false;  

Eratosthenes筛法与分解质因数#

用筛法可以高效地生成质数表，原理不赘述。

memset(not_prime, 0, sizeof(not_prime));  
for(int i=2; i<=n; i++){  
	for(int j=2*i; j<=n; j+=i){  //2i, 3i, 4i...  
		not_prime[j]=1;  
	}  
}  

外层循环次数为n，内层循环次数为 [n/i]-1<n/i，所以总循环次数上限为：$n(1/2 + 1/3 + 1/4 + ... + 1/n) = O(nlogn)$，来源于欧拉的贡献：$1+1/2+1/3+..+1/n=ln(n+1)+\gamma$，$\gamma$为欧拉常数0.577218…

上述算法一般已经能在竞赛中得到10^6^级别的质数表，还可以稍微优化：

• 任何数的质因数小于等于这个数的算术平方根。所以一旦 i 超过了 sqrt(n)，它不会是任何小于等于n的数的约数了，谁也筛不掉，此时，剩下的没被筛掉的都是质数。
• j 可以直接从 I*I 开始。因为比 i 小的数全都已经筛过了，2i, 3i, 4i, …,(i-1)i 都已被筛掉。（要么ki k是质数，被k筛掉，要么k是合数，被k的比i更小的质因数筛掉。

int m=sqrt(n+0.5);  
memset(not_prime, 0, sizeof(not_prime));  
for(int i=2;i<=m;i++){  
	for(int j=i*i; j<=n; j+=i){  
		not_prime[j]=1;  
	}  
}  

素数定理
不超过x的素数的个数
pi(x) ~ x / lnx.

分解质因数

至此分解质因数的问题想出了一种边除边筛的方法。一边生成质数表，一边尝试分解质因数。顺便随着不断让原数变小，能不断缩小sqrt的边界。

vector<int> solution(int n)  
{  
	int not_prime[n];  
	memset(not_prime, 0, sizeof(not_prime));  
	vector<int> ans;  
	int m=n, sqrtm = sqrt(n+0.5);  
	for(int i=2; i<=sqrtm; i++){  
		if(not_prime[i]) continue;  
		bool isans = false;  
		while(m%i==0){  
			isans = true;  
			m /= i;  
			//如果要记录次数，在这里加.  
		}  
		if(isans) ans.push_back(i);  //是质因数.  
		if(m==1) break;  
		//刷掉这个质数的倍数.  
		for(int j=i*i; j<=m; j+=i)  
			not_prime[j]=1;  
	}  
	return ans;  
}  

也可以不必筛的过程！只要从小到大，每遇到一个质数除干净，遇到合数的时候必定是不能整除的！！

扩展欧几里得算法#

这里解决的是 ax+by=c 的整数解的问题。先记结论。

• ax+by=gcd(a,b) 的整数解：

void gcd_line(int a, int b, int& d, int &x, int& y){  
	if(b==0){  
		d = a; x = 1; y = 0;  
	}  
	else{  
		gcd(b, a%b, d, y, x);  
		y -= x*(a/b);  
	}  
}  
这个d貌似就是最后b==0时候的那个a。。？  

• 另一点，ax+by=c，只有当 c 是 gcd(a, b) 的整数倍的时候，才有正整数解。
• 对于使 ax+by=c 的所有解的集合，有一个非齐次特解 (x1, y1)；而齐次方程 ax+by=0 的非零解是（b, -a），可以约掉一个 gcd(a, b)，则所有解为 (x1+b / gcd(a, b), y1-a / gcd(a, b))。如果有整数解，让 (x1, y1) 为整数，k为整数，上面那个就是所有整数解。

取模运算与同余#

两个原先就知道的性质（难点在于用。。）：

• (a+b)%c = ((a%c)+(b%c))%c;
• ab%c = ((a%c)(b%c))%c;

大整数取模
一个非常大的整数，取模方法。
类似秦九韶法 的思路，将大整数表示为：
abcd = ((a*10+b)*10+c)*10+d这样的形式。然后从最里往外一层层算模。
((a%MOD) * (10%MOD) + c%MOD) ......

快速幂取模
略。

同余线性方程组
$ax=b(\mod n)$
表示 ax 与 b 除以n同余。
ax-b = kn，k是整数
变形为 ax-nk = b的整数解，a, n, b 确定，然后求 x, k的整数解。回到了那个扩展欧几里得算法。

值得注意的是，ax=1(mod n) 的解x被称为 a 关于 模 n 的 逆。只有 ax - nk = 1 有整数解的时候才行，这就需要 gcd(a, n)=1.即 a, n 互质的时候a才有模 n 的逆。

数学与暴力
很多时候和数学相关的题确实不能推出神奇的“公式”，就是要枚举尝试！计算机没得猜，就是枚举，有技巧的枚举！
出题人随便找了 三个整数 x1, a, b，用递推公式 xi=(axi-1 + b)%10001 算出了长度为 2T 的序列。输入序列中的奇数项，输出偶数项。

已知 x1，只要“猜出” a, b，就能很简单地推出所有序列。但计算机是不能猜的，它只能枚举。
注意到如果有了 x1，a，待定系数带着 b未知数算出 x3，就可以对照输入解出 b。也就是只用枚举 a 就行了。
由于每次递推的时候，都可以把取模拆成 (axi-1%10001 + b%10001), axi-1%10001 还可以接着拆，a, b大于10000的话是没有意义，或者说和 a%10001的情况是完全等价的。所以a只用枚举 0…10000.
枚举a的时候，算出b，然后递推整个序列，如果在哪个奇数项发现和输入不一样，就说明这个a不对，尝试下一个。

活用取模+*性质！且取模可能与周期相关
巨大的斐波那契。
令 F(n) 为斐波那契数列，求 F(a^b^)%MOD的值。

斐波那契数太大了，何况是那么后的斐波那契！高中类似题目的经验告诉我们，见到这种不妨先写出前几个，看看有没有规律。
从 F(n) = F(n-1) + F(n-2) 来看，F(n)%MOD = ((F(n-1)%MOD)+(F(n-2)%MOD))%MOD，只要有两个连续的余数和前面两个连续的余数一样，后面所有都一样，这就是周期。
而 %n 只有n种余数，两两组合只有 n^2^ 种，由鸽巢原理，前 n^2^+1个里面必然出现相同的连续两个余数。可以直接枚举出来。
然后知周期，用快速幂取模算出是在周期里的哪个位置，即可。

计数#

这里只记不了解的。略加法原理，乘法原理，杨辉三角与二项式定理。重点关注小于n与n互质的数的个数 phi(n)

容斥原理#

n个属性，求具有n个属性之一的个数：具有一个的之和 - 具有两个的之和 + 具有三个的之和 - 具有四个的之和…
具有奇数个性质，是加法，偶数个性质，是减法。
也可以求哪个都不具有的，就是总数 |S| - 上面那个。此时，就是奇数为 - ，偶数为 + 。总之式子中第一个是正，后面全是负就是了。

（质数的欧拉筛法似乎就是基于这个原理。这个筛法比较低效）

小于n与n互质的数的个数 phi(n)#

这是个经常用到的东西。
比如，求小于n 的所有互质数对(a, b)(a<b)个数的方法：

• phi(2)+phi(3)+phi(4)+phi(5)+…+phi(n-1) ········[maybe +phi(n)]

这个方法，还挺简单的。对n分解质因数，假设分解出的质因数为 p1…pk，令性质 i 为这个数的质因数中有 pi。所求为小于n的数中不具有所有性质的数的个数。
这就构成了一个容斥原理。并且小于n的数中，质因数中有 p1, p2, p3…的数的个数是 n / (p1p2p3)，注意这些 p 都是 n 的质因数，都可以整除。
用容斥原理得到的算式非常复杂，计算机不好算。可以转化为以下等式：
$\phi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_n})$
从概率 的角度尝试理解上式：

• 一个前提：小于 n 的 k 的倍数分布是均匀的，（不止倍数，还有模相同的数等等），尤其在 n 整除 k 的时候（不整除，在n大的时候可以近似）。

首先，从所有数中抽取不具有 p1 特性的，由于均匀，概率是 1-(n/p1)/n=1-(1/p1)。剩下的性质中，在抽出来的不具有p1特性的数中仍是“均匀”的，还可以直接抽不具有P2性质的…一直抽完。
可能不对，只是直观解释。

也可以从代数 上理解，将上式直接展开（排列组合式展开）就可以得到直接用容斥原理的式子。

1~n中所有phi值#

算一个 phi 可以直接用上面那个公式，算1~n中所有 phi 的函数值，可以用类似于筛法的方法求出来。 时间复杂度 O(n logn logn)

void phi_table(int n, int[] phi)  
{  
	for(int i=2;i<=n;i++) phi[i]=0;  
	phi[1] = 1;  
	for(int i=2; i<=n; i++){  
		if(phi[i]==0){    //没有被确定，此时i一定是质数，否则一定在之前被其质因数的 j 遍历到。  
			for(int j=i; j<=n; j+=i){  
				if(phi[j]==0) phi[j]=j;  //小于j的j个数一个都没有筛掉  
				phi[j] = phi[j] / i*(i-1); //质数i 是 j的质因数  
				//*(1-1/i)=/i*(i-1)..  
			}  
		}  
	}  
}  

编码问题#

这里主要关于字符串字典序排列的康托编码。 我以前就了解过，这里略。理解为把康托编码的计算过程理解为算比这个串小的串的个数 ，化编码为计数问题，会很好理解。

这里主要讲讲解码的过程，同样是从高到低位尝试，用例子如下：
abcd字典序排列的第8个。
比它小的有7个。
首先是最高位，尝试最小的a，以a开头的有3*2*1=6个。最高位不是a, 7-6=1.
最高位尝试b，此时如果最高位不是b，以b为开头的还有6个，这六个应该都比较小，但此时“余量”只剩1，所以最高位是b。备选中删除b
次高位尝试a，以ba开头的有2个，大于余量1，所以次高位是a. 备选中删除a.
次低位尝试c，以bac开头的只有1个，等于余量1，所以次高位是c, 最低位是d.
结果是 bacd.

离散概率#

原理考的一般不难，都懂，但就是做题很难。这里略吧。。

递推#

卡特兰数#

这里直接给出公式：
$K(n)=\sum_{i+j=n+1}K(i)K(j)$
$K(n+1)=\frac{4n-6}{n}K(n)$
其中 K(2)=K(3)=1

两个例子：

• 凸 n 边形用 n-3 条不相交的对角线分成 n-2 个三角形，求不同分割方法的总数。 （和动态规划的最优三角剖分相似的思路）
• n个0 n个1，求所有前缀中0的个数不少于1的个数的排列方法总数。

其它：随机应变QAQ#

和动态规划等息息相关…对于其分类与转移姑且有两个经验：

• 如果所求的东西中需要有某个性质，可以以“第一次出现此性质的位置”这样分类，一边没有此性质（在这个位置之前），一边随意。
• 构造一个能造出一个解的步骤。还是很抽象…

危险的排列
数量足够多的装有U和L的盒子，把n个盒子排成一行，至少有三个U放在一起，多少种方法？

分类：第一次出现三个U放在一起的位置。假定是 i, i+1, i+2.，则其左边没有三个U放在一起的，右边随意。而没有三个U放在一起的，恰好是所求的补集，用总方法数-所求即可。
令 f 为所求，g = 2^n^ - f 为没有三个U在一起的排列种数。
$f(n)=\sum_{i<=n-2}g(i-1)2^{n-i-2}$

摆旗杆
长度为1,2,3,4,5…n 的旗杆排成一排，从左边看能看到 k 个，右边看能看到 t 个，问一共有几种摆法。

期望与连续概率#

没看，略()。