扩展欧几里德：
ll ex_gcd(ll&x,ll&y,ll a,ll b){
if(!b){x=1,y=0;return a;}
ll r=ex_gcd(x,y,b,a%b);
ll tmp=y;
y=x-a/b*y,x=tmp;
return r;
}
欧拉函数：
int eular(int x){
int ret=1;
for(int i=2;i*i<=x;i++)if(x%i==0){
x/=i,ret*=i-1;
while(x%i==0) x/=i,ret*=i;
}
if(x>1) ret*=x-1;
return ret;
}
斐波那契数列的通项公式：
约瑟夫问题的递推式：
n人喊m的退出,p(i)表示第i个退出的人.
编号0~n-1
p[0] = 0;
p[i] = (p[i-1] + m-1) % (n-i+1);
求和公式：
1+2+3+…+n=(1+n)*n/2;
1^2+2^2+3^2+…+n^2=n*(n+1)*(2*n+1)/6;
1^3+2^3+3^3+…+n^3=((1+n)*n/2 ) ^2;
1^3+3^3+5^3+…+(2*N-1)^3=(n+1)^4/8+ (n+1)^2/4 (n为最后一项)
n很大时：
1+1/2+1/3+1/4+...1/n = ln(n+1) + r (r约为0.5772156649)
卡特兰数：
Ps:cat(1)=cat(2)=1;
一般递归式:
cat(n)=cat(1)*cat(n-1)+h(2)*h(n-2)+…+h(n-1)*h(1) (n>=3);
另类递归式:
cat(n)=cat(n-1)*(4*n-2)/(n+1);
解:cat(n)=C(2n,n)/(n+1)
近似式：cat(n)=4^n/(n^(3/2)*sqrt(pi))
应用:
1. cat(n)表示长度为2n的Dyck
word(n个x,n个y组成的字符串,且从左到右扫描,x的个数大于等于y的)的个数.
2. 将1中的x换成左括号,y换成右括号,cat(n)可以表示含n组括号的合法运算式个数.
3. cat(n)表示有n+1个叶子的二叉树个数.
4. cat(n)表示所有不同构的含n个分支节点的满二叉树的个数.
5. cat(n)表示在nxn格点上所有不越过对角线的最短路径数.(可越过对角线的最短路径数为C(2n,n))
6. cat(n)表示通过连结顶点而将n+ 2边的凸多边形分成三角形的方法个数.
7. 1的变形：m个x,n个y.因为如果一个序列从第k个开始y比x多一个,那么从第k+1个起,x变y,y变x得到一个新序列,这个序列有m+1个y,而且和旧的序列一一对应,所以退出不合法的序列个数为C(m+n,m+1),而一个序列要么合法要么不合法，所以合法序列的个数就是C(m+n,n)-C(m+n,m+1),由于人数不一样所以还要乘以m!*n!,化简之后就是(m+1)!*(m-n+1)/(m+1).
8. 7的推广,如果之前已经排了p个x在最前面,那么同理可证不合法的序列数是C(m+n,m+p+1),化简略.
斯特林公式：
n！= sqrt(2*pi*n)*(n^n)*(e^-n)
错排公式：
m(n) = [ m(n-1) + m(n-2)] * (n-1)
Ps:m(1)=0,m(2)=1;
简化公式:m(n) = {n!/e+0.5}
Ps:{}表示取整数部分
梅森素数(能写成2^p-1的素数，p也为素数)：
int p[41] = {2,3,5,7,13,17,19,31,61,89,107,
127,521,607,1279,2203,2281,3217,4253,4423,
9689,9941,11213,19937,21701,23209,44497,
86243,110503,132049,216091,756839,859433,
1257787,1398269,2976221,3021377,6972593,
13466917,20996011,24036583};
//2^p[]-1为梅森素数