acm 常用数论小总结

《acm 常用数论小总结》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、catlan数令h(0)=1,h(1)＝1,catalan数满足递归式：h(n)=h(0)*h(n-1)+h(1)*h(n-2)+...+h(n-1)h(0)(其中n>=2)该递推关系的解为：h(n)=C(2n,n)/(n+1)(n=1,2,3,...)http://blog.csdn.net/flyupliu/article/details/6547052组合数奇偶性scanf("%d%d",&n,&k);printf("%s",k&(n-k)?"偶数":"奇数");斯特林公式ln(n!)=n*ln(n)-n+1.0/2*ln(2*n*pi)万年历公式week=(ye

2、ar-1+(year-1)div4-(year-1)div100+(year-1)div400+days)mod7week为周几(0为星期日，1为星期一，2为星期二days为这一天在这一年中的第几天lucas定理求c(n,m)modp的值,p是素数。Lucas(n,m,p)=cm(n%p,m%p)*Lucas(n/p,m/p,p)Cm(n,m,p)m>n时return0；Lucas(x,0,p)=1。欧几里得/辗转相除法intgcd(inta,intb){returnb==0?a:gcd(b,a%b);}扩展欧几里得intexgcd(inta,intb,int&x,int&

3、y){if(b==0){x=1,y=0;returna;}intr=exgcd(b,a%b,x,y);inttmp=x;x=y;y=tmp-a/b*y;returnr;}欧拉函数phi(n)=n*(1-1/p1)*(1-1/p2)*...*(1-1/pk);p1p2...为n的素因子表示1...n中与n互质的数的个数推导概率解释ex：[1,a]与[1,b]互质对个数？欧拉定理&费马小定理欧拉定理：若n,a为正整数，且n,a互质，(a,n)=1，则a^φ(n)≡1(modn)费马小定理：假如p是质数，且gcd(a,p)=1，那么a^(p-1)≡１（modp）容斥原理ex：所有

4、小于100的正整数中有因子2或3的数的个数？ans=100/2+100/3-100/6这就是容斥原理^^!容斥原理dfshdu4059java大数default.......中国剩余定理ex：一个数被3除余1，被4除余2，被5除余4，这个数最小是几？http://hi.baidu.com/%D7%CF%B5%E7%CC%DA%F2%D4/blog/item/53fb06ab50b091eefaed50b7.htmlmiller_rabin素数测试利用费尔马小定理,对于给定的整数n,可以设计素数判定算法,通过计算d=a^(n-1)%n来判断n的素性当d!=1时,n肯定不是素数

5、当d=1时,n可能不是素数1/4.二次探测定理:如果p是一个素数,且0

6、t(n))。pollard-rho大整数质因数分解(2)伪代码：intpollard_rho(n){x=y=x0while(d==1){x=f(x),y=f(f(y))d=gcd(x–y,n)if1

7、.Thediscretelogproblemisoffundamentalimportancetotheareaofpublickeycryptography.Manyofthemostcommonlyusedcryptographysystemsarebasedontheassumptionthatthediscretelogisextremelydifficulttocompute;themoredifficultitis,themoresecurityitprovidesadatatransfer.Onewa