1.一个数的约数和=(1+p1+p12+...+p1c1)*(1+p2+p22+...+p2c2)*...*(1+pk+pk2+...+pkck)（p为这个数的各个质因数，c表示为各个质因数的次方，k表示质因数个数）
2.求一个数的质因数只需要O(sqrt(n))的时间复杂度，先筛出素数，然后将原数除去小素数，如果原数最后不为1，那么这个数肯定也是素数
3.相邻的数交换使得最终成为上升序列，交换的次数为逆序对数
4.费马小定理：若p为质数，则$a^{p}≡a(mod;p)$
5.欧拉定理：若正整数a,n互质，则$a^{phi(n)}≡1(mod;n)$
6.一个正整数n，设它其中一个约数为p，那么gcd(i,n)==p的有$phi(n/p)$个
7.欧拉定理推论：若正整数a,n互质，则对于任意正整数b，有$a^{b}≡a^{b;mod;phi(n)}(mod;n)$
8.乘法逆元：若整数b,p互质，并且b|a，则存在一个整数x，使得a/b≡a*x(mod p)，则称x为b的模p乘法逆元，当模数p为质数时，bp-2即为b的乘法逆元，也就是b-1≡bp-2(mod p)
9.中国剩余定理(crt)：设m1,m2,...,mn是两两互质的整数，$m=prod_{i=1}^{n}m_{i}$，Mi=m/mi，ti是线性同余方程Miti≡1(mod mi)的一个解,对于任意的n个整数a1,a2,...,an，方程组：x≡a1(mod m1),x≡a2(mod m2),...,x≡an(mod mn)，有整数解，且解为$x=sum_{i=1}^{n}a_{i}M_{i}t_{i}$
10.二项式定理：$(a+b)^{n}=sum_{k=0}^{n}C_{n}^{k}a^{k}b^{n-k}$
11.Lucas定理：若p是质数，则对于任意整数1<=m<=n，有：$C_{n}^{m}=C_{n;mod;p}^{m;mod;p}*C_{n/p}^{m/p}(mod;p)$
12.Catalan数列：给定n个0，n个1，他们按照某种顺序排成长度为2n的序列，满足任意前缀中0的个数都不少于1的个数的序列的数量为$Cat_{n}=frac{C_{2n}^{n}}{n+1}$
Catalan数推论：
(1).n个左括号和n个右括号组成的合法括号序列的数量为Catn
(2).1,2,...,n经过一个栈，形成的合法出栈序列的数量为Catn
(3).n个节点构成的不同二叉树的数量为Catn
(4).在平面直角坐标系上，每一步只能向上或向右走，从(0,0)走到(n,m)并且除两个端点外不接触直线y=x的路线数量为2Catn-1
13.莫比乌斯函数的性质：
(1).对于一个数d，如果d=1，$mu(d)=1$，如果d为互异质数p1p2p3...pk的乘积，则$mu(d)=(-1)^{k}$，否则$mu(d)=0$
(2).$sum_{d|x}mu(d)=[x==1]$
(3).对于任意正整数n有：$sum_{d|n}frac{mu(d)}{d}=frac{phi(n)}{n}$
(4).$sum_{d|x}phi(d)=x$
莫比乌斯反演：
(1).如果存在函数F(x)和f(x),满足$F(n)=sum_{d|n}f(d)$，则可以得到$f(n)=sum_{d|n} mu(d)F(frac{n}{d})$
(2).如果存在函数F(x)和f(x),满足$F(n)=sum_{n|d}f(d)$，则可以得到$f(n)=sum_{n|d}mu(frac{d}{n})F(d)$
14.序列错排求解：对于一个长度为n的序列，n个数互不相同且均为1到n的数，使得一个序列中第i个位置都不等于i的序列数量为$D(n)$。令$D(0)=1,D(1)=0$，得$D(n)=(n-1)*(D(n-1)+D(n-2))$
15.对于一个n*m的图，只能向右或向下行走，从左上角走到右下角的方案数为$C_{n+m-2}^{n-1}$
16.快速求自然数幂和$sum_{i=1}^{n}i^{k}mod p$的几种方法
(1).差分表，$S(n,k)=sum_{i=1}^{n}i^{k}$
公式：$S(n,k)=frac{1}{k+1} left( (n+1)^{k+1}-n-1-sum_{i=2}^{k}C_{k+1}^{i}S(n,k-i+1) ight )$
复杂度：$O(k^{2})$
(2).伯努利数，$B_{0}=1$
因为$sum_{j=0}^iC_{i+1}^jB_j=0$
所以$B_i=-frac{1}{i+1}sum_{j=0}^{i-1}C_{i+1}^{j}B_j$
公式：$sum_{i=1}^{n}i^k={1over{k+1}}sum_{i=1}^{k+1}C_{k+1}^i*B_{k+1-i}*(n+1)^i$
复杂度：$O(Tk)$T为数据组数
17.1到x中，与x互质的数的和为$frac{phi(x)*x}{2}$，特殊的，当x=1时，数和为0
18.等比数列$S_{n}=frac{a_1(1-q^n)}{1-q}$,$S_n$为前n项的和，$a_1$为首项，$q$为公比