ACM-常用数论小总结.pptVIP

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,...) /flyupliu/article/details/6547052 组合数奇偶性 scanf(%d%d, n, k); printf(%s\n, k(n-k)? 偶数: 奇数); 斯特林公式 ln(n!) = n * ln(n) - n + 1.0/2 * ln(2 * n * pi) 万年历公式 week = (year-1 + (year-1) div 4 - (year-1) div 100 + (year-1) div 400 + days) mod 7 week为周几(0为星期日，1为星期一，2为星期二 days为这一天在这一年中的第几天 lucas定理 求c(n,m) mod p的值,p是素数。 Lucas(n,m,p)=cm(n%p,m%p)*Lucas(n/p,m/p,p) Cm(n, m, p) m n 时 return 0； Lucas(x,0,p)=1。 欧几里得/辗转相除法 int gcd(int a, int b) { return b==0? a: gcd(b, a % b) ; } 扩展欧几里得 int exgcd(int a, int b, int x, int y) { if(b == 0){ x = 1, y = 0; return a;} int r = exgcd(b, a % b, x, y); int tmp = x; x = y; y = tmp - a/b * y; return r; } 欧拉函数 phi(n) = n*(1 - 1/p1)*(1 - 1/p2)*...*(1 - 1/pk); p1 p2 ... 为n 的素因子 表示 1 ... n 中 与 n 互质的数的个数 推导 概率解释 ex： [1, a] 与 [1, b] 互质对个数 ？ 欧拉定理 费马小定理 欧拉定理：若n,a为正整数，且n,a互质，(a,n) = 1，则a^φ(n) ≡ 1 (mod n) 费马小定理：假如p是质数，且gcd(a,p)=1，那么 a^(p-1) ≡１（mod p） 容斥原理 ex： 所有小于 100 的正整数中 有因子2 或3 的数的个数 ？ ans = 100 / 2 + 100 / 3 - 100 / 6 这就是容斥原理 ^ ^ ! 容斥原理 dfs hdu 4059 java大数 default ....... 中国剩余定理 ex： 一个数被3除余1，被4除余2，被5除余4，这个数最小是几？ /%D7%CF%B5%E7%CC%DA%F2%D4/blog/item/53fb06ab50b091eefaed50b7.html miller_rabin 素数测试 利用费尔马小定理,对于给定的整数n,可以设计素数判定算法,通过 计算d=a^(n-1)%n来判断n的素性 当d!=1时,n肯定不是素数 当d= 1时,n可能不是素数 1/4. 二次探测定理:如果p是一个素数,且0xp,则方程x^2%p=1的解为:x=1或 x=p-1. Miller_Rabin测试T次时，它产生一个假的素数所花费的时间不超过1/4^T pollard-rho大整数质因数分解 它的核心思想是：选取一个随机数a。再选一个随机数b。检查d = gcd(a-b, n) 是否大于1。若大于1，d就是n的一个因子。否则再选取随机数c，检查gcd(a - c, n)和gcd(b - c, n)。如此继续，直到找到n的一个非平凡因子。 在最坏情况下，其时间复杂度可能接近sqrt(n)，但在一般条件下，时间复杂度都可以认为是 sqrt( sqrt(n) )。 pollard-rho大整数质因数分解(2) 伪代码： int pollard_rho(n) { x = y = x0 while (d == 1) { x = f(x), y = f(f(y)) d = gcd(x – y, n) if 1 d AND d n then return d if d == n then return FAILURE } } baby-giant step wiki上的的算法: In group theory, a branch of mathem