数学公式集锦

1错排公式HDU1465

a[1]=0;a[2]=1;

a[i]=(i-1)*(a[i-1]+a[i-2]);

2----求卡特兰数

令h(0)=1,h(1)=1，catalan数满足递推式^[1]：

h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (n>=2)

例如：h(2)=h(0)*h(1)+h(1)*h(0)=1*1+1*1=2

h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=1*2+1*1+2*1=5

另类递推式^[2]：

h(n)=h(n-1)*(4*n-2)/(n+1);

递推关系的解为：

h(n)=C(2n,n)/(n+1) (n=0,1,2,...)

递推关系的另类解为：

h(n)=c(2n,n)-c(2n,n+1)(n=0,1,2,...)

3 欧拉函数，求小于m与m互质数的个数

 1 int eo(int m)
 2 {
 3     int i;
 4     int s=1;
 5     for(i=2; i*i<=m; i++)
 6     {
 7         if(m%i==0)
 8         {
 9             m/=i;
10             s*=i-1;
11             while(m%i==0)
12             {
13                 m/=i;
14                 s*=i;
15             }
16         }
17     }
18     if(m>1)
19         s*=m-1;
20     return s;
21 }
22 
23

View Code

欧拉定理的内容是：如果a和n互质，那么a^φ(n)=1(mod n)；对于任意a,
n和较大的b，有a^b=a^{φ(n)+b mod φ(n)}(mod n)。

4 中国剩余定理求同余最小被除数

 1 unsigned int ResidueTheorem(const unsigned int devisor[], const unsigned int remainder[], int length)　　
 2 {
 3 　　unsigned int product = 1; //所有除数之乘积
 4 　　for(int i=0; i<length; i++) //计算所有除数之乘积
 5 　　{
 6 　　    product *= devisor[i];
 7     }
 8 　　//公倍数数组，表示除该元素（除数）之外其他除数的公倍数
 9 　　unsigned int *commonMultiple = new unsigned int(length);
10 　　for(int i=0; i<length; i++) //计算除该元素（除数）之外其他除数的公倍数
11 　　{
12 　　    commonMultiple[i] = product / devisor[i];
13     }
14 　　unsigned int dividend = 0; //被除数，就是函数要返回的值
15 　　for(int i=0; i<length; i++) //计算被除数，但此时得到的不是最小被除数
16 　　{
17 　　    unsigned int tempMul = commonMultiple[i];
18 　　    //按照剩余理论计算合适的公倍数，使得tempMul % devisor[i] == 1
19 　　    while(tempMul % devisor[i] != 1)
20 　　    {
21 　　        tempMul += commonMultiple[i];
22         }
23 　　    dividend += tempMul * remainder[i]; //用本除数得到的余数乘以其他除数的公倍数　
24     }
25 　　delete []commonMultiple;
26 　　return (dividend % product); //返回最小被除数
27 }

View Code