acm-常用的数学公式.doc

1、常用公式2划分问题：3Stirling公式3皮克定理3卡特兰数4错排公式4等比数列5等差数列5二次函数6二次方程7约瑟夫环7多边形面积7均值不等式的简介8均值不等式的变形8Lucas 定理9斐波那契数列10欧拉函数11蚂蚁爬绳12(a/b)%m13泰勒公式13乘法与因式分解公式14三角不等式14某些数列的前n项和15二项式展开公式15三角函数公式16常用公式三角不等式|a+b|a|+|b|a-b|a|+|b|a|b-bab|a-b|a|-|b|-|a|a|a|一元二次方程的解-b+(b2-4ac)/2a -b-(b2-4ac)/2a根与系数的关系X1+X2=-b/aX1*X2=c/a注：韦达定

2、理数列前n项和1+2+3+4+5+6+7+8+9+n=n(n+1)/21+3+5+7+9+11+13+15+(2n-1)=n22+4+6+8+10+12+14+(2n)=n(n+1)12+22+32+42+52+62+72+82+n2=n(n+1)(2n+1)/613+23+33+43+53+63+n3=n2(n+1)2/41*2+2*3+3*4+4*5+5*6+6*7+n(n+1)=n(n+1)(n+2)/3常用数学公式表:解析几何公式圆的标准方程 (x-a)2+(y-b)2=r2注：（a,b）是圆心坐标圆的一般方程 x2+y2+Dx+Ey+F=0注：D2+E2-4F0抛物线标准方程y2=2

3、pxy2=-2pxx2=2pyx2=-2py常用数学公式表:几何图形公式直棱柱侧面积 S=c*h斜棱柱侧面积S=c*h正棱锥侧面积 S=1/2c*h正棱台侧面积 S=1/2(c+c)h圆台侧面积 S=1/2(c+c)l=pi(R+r)l球的表面积 S=4pi*r2圆柱侧面积 S=c*h=2pi*h圆锥侧面积 S=1/2*c*l=pi*r*l弧长公式l=a*r (a是圆心角的弧度数r0) 扇形面积公式s=1/2*l*r锥体体积公式V=1/3*S*H圆锥体体积公式V=1/3*pi*r2h柱体体积公式V=s*h圆柱体 V=pi*r2h斜棱柱体积 V=SL (S是直截面面积，L是侧棱长) 注：pi=a

4、cos(-1.0);划分问题：1、 n个点最多把直线分成C(n,0)+C(n,1)份； 2、n条直线最多把平面分成C(n,0)+C(n,1)+C(n,2)份； 3、n个平面最多把空间分成C(n,0)+C(n,1)+C(n,2)+C(n,3)=(n+5n+6)/6份； 4、n个空间最多把“时空”分成C(n,0)+C(n,1)+C(n,2)+C(n,3)+C(n,4)份.Stirling公式lim(n) (2n) * (n/e)n= n! 也就是说当n很大的时候,n!与(2n) * (n/e) n的值十分接近这就是Stirling公式. (2n) 0.5 n n e(-n) =n!;皮克定理一个多

5、边形的顶点如果全是格点，这多边形就叫做格点多边形。有趣的是，这种格点多边形的面积计算起来很方便，只要数一下图形边线上的点的数目及图内的点的数目，就可用公式算出。 这个公式是皮克(Pick)在1899年给出的，被称为“皮克定理”，这是一个实用而有趣的定理。 给定顶点坐标均是整点（或正方形格点）的简单多边形，皮克定理说明了其面积S和内部格点数目a、边上格点数目b的关系：S=a+ b/2 - 1。(其中a表示多边形内部的点数,b表示多边形边界上的点数,S表示多边形的面积)卡特兰数原理:令h(1)1,h(0)=1，catalan数满足递归式：h(n)= h(0)*h(n-1)+h(1)*h(n-2)

6、+ . + h(n-1)h(0) (其中n=2)另类递归式：h(n) = h(n-1)*(4*n-2)/(n+1);该递推关系的解为：h(n)=C(2n,n)/(n+1) (n=1,2,3,.)卡特兰数的应用（实质上都是递归等式的应用）错排公式当n个编号元素放在n个编号位置,元素编号与位置编号各不对应的方法数用M(n)表示,那么M(n-1)就表示n-1个编号元素放在n-1个编号位置,各不对应的方法数,其它类推.第一步,把第n个元素放在一个位置,比如位置k,一共有n-1种方法;第二步,放编号为k的元素,这时有两种情况.1,把它放到位置n,那么,对于剩下的n-2个元素,就有M(n-2)种方法;2,

7、不把它放到位置n,这时,对于这n-1个元素,有M(n-1)种方法;综上得到递推公式：M(n)=(n-1)M(n-2)+M(n-1) 特殊地，M(1)=0,M(2)=1通项公式：M(n)=n!(-1)2/2!+(-1)(n-1)/(n-1)!+(-1)n/n!优美的式子：Dn=n!/e+0.5,x为取整函数 公式证明较简单观察一般书上的公式，可以发现e-1的前项与之相同，然后作比较可得/Dn-n!e-1/1/(n+1)0时，开口方向向上，a0时，开口方向向下。a的绝对值还可以决定开口大小,a的绝对值越大开口就越小,a的绝对值越小开口就越大。）yax2bxc 二次方程a*x+b*y+c=0;当0

8、，x1= -b-sqrt(b*b-4*a*c)/(2*a)，x2=-b+ sqrt(b*b-4*a*c)/(2*a)。约瑟夫环令f表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是fn.递推公式:f1=0;f=(fi-1+m)%i; (i1)有了这个公式，我们要做的就是从1-n顺序算出f的数值，最后结果是fn。因为实际生活中编号总是从1开始，我们输出fn+1由于是逐级递推，不需要保存每个f，程序也是异常简单：多边形面积点顺序给出S=0.5*abs(x1*y2-y1*x2+x2*y3-y2*x3+.+xn*y1-yn*x1) 均值不等式的简介概念：1、调和平均数：Hn=n/(1/a1+1

9、/a2+.+1/an)2、几何平均数：Gn=(a1a2.an)(1/n)=n次(a1*a2*a3*.*an)3、算术平均数：An=(a1+a2+.+an)/n4、 平方平均数：Qn= (a12+a22+.+an2)/n5、 这四种平均数满足:HnGnAnQna1、a2、 、anR +，当且仅当a1=a2= =an时取“=”号均值不等式的一般形式：设函数D(r)=（a1r+a2r+.anr）/n(1/r) (当r不等于0时);(a1a2.an)(1/n)(当r=0时）（即D(0)=(a1a2.an)(1/n)）则有：当r0-2ab(2)对非负实数a,b，有a+b2(a*b)0，即(a+b)/2(

10、a*b)0(3)对负实数a,b，有a+b0=(abc)(1/3)(11) a3+b3+c3=3abc,a、b、c都是正数。扩展：若有y=x1*x2*x3.Xn 且x1+x2+x3+.+Xn=常数P,则Y的最大值为(x1+x2+x3+.+Xn)/n)n 1、| |a|-|b| |a-b|a|+|b| 2、| |a|-|b| |a+b|a|+|b|设a1,a2,an；b1,b2bn均是实数，且a1a2a3an,b1b2b3bn;则有a1b1+a2b2+anbn（顺序和）a1b2+a2b1+a3b3+aibj+anbm（乱序和）a1bn+a2bn-1+a3bn-2+anb1（逆序和）,仅当a1=a2

11、=a3=an,b1=b2=b3=bn时等号成立。 Lucas 定理斐波那契数列欧拉函数实际使用的时候是用下面这个式子：在程序中利用欧拉函数如下性质，可以快速求出欧拉函数的值(a为N的质因素)(1) 若(N%a=0 & (N/a)%a=0) 则有:E(N)=E(N/a)*a;(2) 若(N%a=0 & (N/a)%a!=0) 则有:E(N)=E(N/a)*(a-1);欧拉函数的值（小于等于1的正整数中唯一和1互质的数就是1本身）。若n是质数p的k次幂，因为除了p的倍数外，其他数都跟n互质。欧拉函数是积性函数，即是说若m,n互质，。证明：设A, B, C是跟m, n, mn互质的数的集，据中国剩余

12、定理，和C可建立双射(一一对应)的关系。因此的值使用算术基本定理便知，若 则。 例如先看（2）式，N%a=0 & (N/a)%a!=0，因为a是质数，而N/a不能被a整除，说明N/a与a互质，由上面的可知E(N)=E(N/a)*E(a);而E(a)=a-1 （因为按照欧拉函数定义欧拉函数是小于或等于n的正整数中与n互质的数的数目，a为质数，从1到a-1都和a互质，所以E(a)=a-1）,故E(N)=E(N/a)*(a-1);再看（1）式，由于a是N/a的质因数，不能像（2）一样用上面的积性函数的公式。那看这个式子，假设E(n)可以表示成ak*(a-1)*C，C为后面的部分，则E(n/a)可以表

13、示成a(k-1)*(a-1)*C，比较两式的差别可以得到E(n)是E(n/a)的a倍，即E(N)=E(N/a)*a。其实，（2）式也可以像（1）式一样证明，因为N/a与a互质，说明N的质因数有且只有一个a，则E(n)可表示为(a-1)*C，E(N/a)可表示为C，比较两式差别可以得到E(N)=E(N/a)*(a-1).蚂蚁爬绳一绳长L米，一蚂蚁从绳的一端爬向另一端，速度为每秒v m/s，同时，绳子以每秒u 米的速度均匀伸长，问：蚂蚁能否达到绳的另一端？如能，需多长时间？如不能，请说明理由。（假设绳子质量无限好，蚂蚁寿命无限长）T=e(u/v)-1*L/u;(a/b)%m背景：a是b的倍数1.如

14、果m是质数，很简单，直接用扩展的欧几里德求b关于m的逆元对于 a/b%m = ans, 求 ans。a = a%m, b = b%mans = (a % m)*(x % m) % m （x为b的逆元）求逆元则利用扩展欧几里德：对于 b*x = 1(mod m)可以求b*x + m*y = 1的解（ 用extennd_Euclid(b, m, x, y) )!然后把 x 映射到 0,m)区间，带入上式， 即得解。2.如果m不是质数，把m质数分解成质数p1,p2,pk的积然后把a分解成a1*a2，其中a1的质因数只能在p中，a2与p中的所有质数都互质，即a2与m互质同理把b分解成b1*b2，其中b

15、1的质因数只能在p中，b2与p中的所有质数都互质，即b2与m互质3.现在问题变成了(a1*a2)/(b1*b2)%m，即(a1/b1)%m*(a2/b2)%m。问题分解成了两个问题:对于a1/b1%m，可以化为:(p1m1*p2m2*pkmk)/(p1n1*p2n2*pknk)%m， 即:p1(m1-n1)*p2(m2-n2)*pk(mk-nk)%m对于a2/b2%m，b2与m互质，则可以直接求出b2关于m的逆元化为a2*b2(-1)%m.4.于是，问题解决，时间复杂度约为O(sqrt(m) + log(m)泰勒公式乘法与因式分解公式1.2 1.4 三角不等式2.1 2.2 2.3 2.4 2.6 某些数列的前n项和 4.2 4.3 4.7 二项式展开公式三角函数公式1 两角和公式2 倍角公式6.5 6.6 3 半角公式 4 和差化积17