排列组合：
C(n,k) + C(n,k+1) = C(n+1,k+1)
从n+1个数里面选择k+1个数，可以转化成分析是否选第一个数
①如果选了，则转化成n个数里面选k个
②如果没选，则转化成n个数里面选k+1个
C(n,k+1) = C(n,k) * (n-k)/(k+1)
借此可以从C(n,0)递推到C(n,n)得出所有排列 /*O(n)的复杂度
重复元素的排列：
有k个元素，第i个元素的个数为n[i]。假设所有数都是不同的得出n！
但对于每个相同的数有n[i]！中排列可能，所以n[1]!*n[2]!......*n[k]!*x = n!,求出x即可
可重复选择的组合：
有n个元素，每个可以多次选择，选k个元素有多少种方法
类似于把k个球放到n个盒子当中，每个盒子可以放入多个，问有多少种方法
假设对n+k-1个点画n-1条分界线，球数为 所得个数-1。
C(k+n-1,n-1) = C(k+n-1,k)
对于给定的n个点，没有三点共线，没两个点之间用红色或者黑色的线段连接。
求三边同色的三角形个数：
反面考虑，只需求出非单色的三角形的个数便能间接得到三角形的个数，对于第i个点，假设有a[i]个黑边，则它有
n-1-a[i]条红边，则可以构成a[i]*(n-1-a[i])个非同色三角形，由于每个三角形考虑了两次，除以2即可
uva14401 //机制的转换成数学问题
有1~n的n个整数，选出三个不同的整数，使得他们可以形成三角形。（3≤n≤1000000）
假设最大边x有c(x)个,y+z>x,所以 x-y<z<x,当y = x-1时,z有x-2个值。
一共有0+1+2......+x-2 = (x-2)*(x-1)/2个值。
但是其中有y = z的情况,y取值[x/2+1,x-1]共有(x-1)/2个
于是乎，枚举每个x，递推出最终答案。
void solve()
{
for(int x = 4;x <= n;x++)
{
f[x] = f[x-1] + ((x-1)*(x-2)/2 - (x-1)/2)/2;
}
}
Fibonacci数的矩阵实现
F[n] = F[n-1]+F[n-2]
欧拉函数：
得出[1,n-1]中与n互质的数的个数。
①：当n是素数p的k次幂，则phi[n] = p^k - p^(k-1) = (p-1)*p(k-1)
②：当a，b互质时，phi[a*b] = phi[a]*phi[b];
③：如果a,m是互质的正整数，则a^phi(m) = 1(mod m)
④：如果n为奇数，则phi[2*n] = phi[n],
⑤：如果n大于2，那么n的欧拉函数值是偶数
⑥：设p为质数，以减去能与p^n相约的数,即p^n/p,所以：phi[p^n] = p^n - p^(n-1)
Uva 11426
给你一个n，求1≤a<b≤n,gcd(a,b)的和。对于每一个[1,n]数t,枚举x,我们需要知道gcd(x,t) = i的个数，
所以等同于gcd(a/i,b/i) = 1的个数,值为i*gcd(a/i,b/i),预处理即可。
费马小定理 ( 如果p为质数且a，p互质 a^(p-1) = 1(mod p) )
a^n = a^(n%(p-1))*a^(p-1)*..... = a^(n%(p-1))
所以：
反素数：
对于任何正整数
数
1.一个反素数的质因子必是从2开始的质数
2.如果
for(int i = 2; i*i <= m ; i ++)
{
if(m % i == 0)
{
pm[cur] = i;
while(m % i == 0)
{
m /= i;
nm[cur]++;
}
cur++;
}
}