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，有ab=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
转载于:https://www.cnblogs.com/Skyxj/p/3200823.html
