《ACM算法竞赛模板个人总结》由会员分享，可在线阅读，更多相关《ACM算法竞赛模板个人总结（109页珍藏版）》请在金锄头文库上搜索。
1、数 学.4 最大公约数、最小公倍数.4 最大公约数欧几里得算法 O(n).4 Stein 算法 O( log(max(a,b) ).4 最小公倍数：.4 素数相关.5 普通素数判断.5 筛法求素数1，N.5 二次筛法求素数L，R.6 Miller-Rabbin 素数测试方法.7 算术基本定理的定义和性质：.8 同余方程组 乘法模逆元 中国剩余定理.9 扩展欧几里得，求一组解 x，y，使得 gcd(a,b) = d = a * x + b * y.9 扩展欧几里得，求所有解 x，y，使得 c = a * x + b * y.10 扩展欧几里得，求 a 关于 n 的逆元 a-1，使得 a * a-
2、1 1(mod n).10 扩展欧几里得，求解 x，满足同余方程组 x Ri(mod Ai).10 扩展欧几里得，求解 x，满足高次同余方程 Ax B(mod C).11 中国剩余定理：.13 中国剩余定理最小非负数解的算法：.14 求解 a*x + b*y = c 的其中一组解，使得|x| + |y|尽可能小，若相等，则 a|x| + b|y|尽可能小。.15 整数快速幂.16 矩阵快速幂.16 整数分解.18 试除法整数分解.18 筛法整数分解.18 PollardRho 大整数分解.19 欧拉函数.22 直接欧拉函数.22 递推快速求欧拉函数.23 容斥原理.23 母函数.24 普通母函
3、数.24 指数型母函数.25 其他相关.27 九余数定理：一个数 N 各位数字的和，对 9 取余等于这个数对 9 取余.27 给你一个奇数 N，求 1N 的奇数平方和： S = N*(N+1)*(N+2)/6.27 约瑟夫问题：有 N 个人，编号为 1N，按顺时针围成一个圈，每数 k 个人，就将 这个人从圈中消除，问：最终只留下一个人的编号。.27 给你整数 x 和 y 的和以及 x 和 y 的积，是否能找到满足这两个式子的整数 x 和整 数 y。.29 Fibonacci 数列大于 40 前四位数字.29 小于 N 的素数个数为 (N),(N)的位数是多少？.29 Stirling 公式：当 N 足够大时，N! = (N/e) * N * sqrt(2*pi*N)。.29有 N 张卡，将 N 张卡分成若干不同的集合，集合不能为空。问：总共有多少种分 法。.29 字符串.2
