ACM算法竞赛模板个人总结教程.doc

TOC \o 1-3 \h \u  HYPERLINK \l _Toc18320 数 学  PAGEREF _Toc18320 4  HYPERLINK \l _Toc19917 最大公约数、最小公倍数  PAGEREF _Toc19917 4  HYPERLINK \l _Toc14284 最大公约数——欧几里得算法O(n)  PAGEREF _Toc14284 4  HYPERLINK \l _Toc12123 Stein算法O( log(max(a,b)) )  PAGEREF _Toc12123 4  HYPERLINK \l _Toc25854 最小公倍数：  PAGEREF _Toc25854 4  HYPERLINK \l _Toc30801 素数相关  PAGEREF _Toc30801 5  HYPERLINK \l _Toc17934 普通素数判断  PAGEREF _Toc17934 5  HYPERLINK \l _Toc6249 筛法求素数[1，N]  PAGEREF _Toc6249 5  HYPERLINK \l _Toc13973 二次筛法求素数[L，R]  PAGEREF _Toc13973 6  HYPERLINK \l _Toc1163 Miller-Rabbin素数测试方法  PAGEREF _Toc1163 7  HYPERLINK \l _Toc10407 算术基本定理的定义和性质：  PAGEREF _Toc10407 8  HYPERLINK \l _Toc15367 同余方程[组] 乘法模逆元 中国剩余定理  PAGEREF _Toc15367 9  HYPERLINK \l _Toc17851 扩展欧几里得，求一组解x，y，使得gcd(a,b) = d = a * x + b * y  PAGEREF _Toc17851 9  HYPERLINK \l _Toc21586 扩展欧几里得，求所有解x，y，使得c = a * x + b * y  PAGEREF _Toc21586 10  HYPERLINK \l _Toc32738 扩展欧几里得，求a关于n的逆元a^-1，使得a * a^-1 ≡ 1(mod n)  PAGEREF _Toc32738 10  HYPERLINK \l _Toc10215 扩展欧几里得，求解x，满足同余方程组x ≡ Ri(mod Ai)  PAGEREF _Toc10215 10  HYPERLINK \l _Toc23983 扩展欧几里得，求解x，满足高次同余方程A^x ≡ B(mod C)  PAGEREF _Toc23983 11  HYPERLINK \l _Toc26878 中国剩余定理：  PAGEREF _Toc26878 13  HYPERLINK \l _Toc24199 中国剩余定理最小非负数解的算法：  PAGEREF _Toc24199 14  HYPERLINK \l _Toc7995 求解a*x + b*y = c的其中一组解，使得|x| + |y|尽可能小，若相等，则a|x| + b|y|尽可能小。  PAGEREF _Toc7995 15  HYPERLINK \l _Toc551 整数快速幂  PAGEREF _Toc551 16  HYPERLINK \l _Toc3963 矩阵快速幂  PAGEREF _Toc3963 16  HYPERLINK \l _Toc5540 整数分解  PAGEREF _Toc5540 18  HYPERLINK \l _Toc18284 试除法整数分解  PAGEREF _Toc18284 18  HYPERLINK \l _Toc14648 筛法整数分解  PAGEREF _Toc14648 18  HYPERLINK \l _Toc4764 PollardRho大整数分解  PAGEREF _Toc4764 19  HYPERLINK \l _Toc28045 欧拉函数  PAGEREF _Toc28045 22  HYPERLINK \l _Toc3343 直接欧拉函数  PAGEREF _Toc3343 22  HYPERLINK \l _Toc11381 递推快速求欧拉函数  PAGEREF _Toc11381 23