1数学在算法里的位置
想一道你做过的、靠数学而不是靠代码解决的题。
算法进阶 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 页 · 正面（题目）
2整除与同余
模 3 意义下，整数被分成几类？
3同余的性质
为什么减法要小心？
4最大公约数的性质
已知 gcd 是 6，两数是 12 和 18，lcm 是多少？
5扩展欧几里得
这个能用来做什么？
6线性同余方程
为什么要有这个条件？
7中国剩余定理
这个定理古代用来做什么？
8欧拉函数
12 的欧拉函数是多少？
9费马小定理
怎么用它求逆元？
10筛法求欧拉函数
预处理的好处是什么？
第 1 页 · 背面（答案）
参考答案（家长）：三类，余 0、余 1、余 2。
参考答案（家长）：如求和公式、组合计数、判质数的优化。
参考答案（家长）：36。
参考答案（家长）：可能出现负数，要先加模数再取模。
参考答案（家长）：等式两边都是那个公约数的倍数，b 不是就无解。
参考答案（家长）：求逆元、解线性同余方程。
参考答案（家长）：4（1、5、7、11）。
参考答案（家长）：韩信点兵 —— 通过几次报数确定人数。
参考答案（家长）：之后每次查询都是常数时间。
参考答案（家长）：a 的逆元等于 a 的 p-2 次方模 p，用快速幂算。
第 2 页 · 正面（题目）
11约数个数与和
12 等于 2 的平方乘 3，约数有几个？
12排列与组合再练
从 10 人中选 3 人组队，是排列还是组合？
13组合恒等式
这第二条对应杨辉三角的什么性质？
14隔板法
10 个球放 3 个盒子（可空）有多少种？
15错排问题
3 个人的错排有几种？
16卡特兰数
3 对括号有多少种合法排列？
17容斥再练
1 到 100 中被 2 或 3 整除的有多少个？
18概率基础
连掷两次骰子都是 6 的概率？
19期望的线性性
掷两个骰子点数之和的期望？
20期望 DP
为什么倒着推？
第 2 页 · 背面（答案）
参考答案（家长）：组合。
参考答案（家长）：3 乘 2 等于 6 个。
参考答案（家长）：从 12 个位置里选 2 个放隔板。
参考答案（家长）：每个数等于上面两个之和。
参考答案（家长）：5 种。
参考答案（家长）：2 种。
参考答案（家长）：三十六分之一。
参考答案（家长）：50 加 33 减 16 等于 67 个。
参考答案（家长）：终止状态的期望已知，从它往回推最自然。
参考答案（家长）：3.5 加 3.5 等于 7。
第 3 页 · 正面（题目）
21数论练习一
该用什么？
22数论练习二
该怎么做？
23数论练习三
该用什么定理？
24位运算技巧
怎么判断 n 是不是 2 的幂？
25二进制枚举子集
n 是 4 时有多少个子集？
26枚举子集的子集
为什么是 3 的 n 次方？
27异或的性质
找出只出现一次的数，怎么做？
28异或前缀和
这和加法前缀和的差别在哪？
29线性基直觉
这和线性代数里的基是一回事吗？
30博弈论：必胜与必败
终止状态（不能再走）是什么态？
第 3 页 · 背面（答案）
参考答案（家长）：预处理阶乘和阶乘逆元，每次查询常数时间。
参考答案（家长）：分解质因数后用欧拉函数公式。
参考答案（家长）：n 大于 0 且 n 与 n-1 的按位与等于 0。
参考答案（家长）：中国剩余定理。
参考答案（家长）：每个元素有三种状态：不在集合、在集合但不在子集、在子集。
参考答案（家长）：16 个，包括空集。
参考答案（家长）：加法要减，异或还是异或。
参考答案（家长）：把所有数异或起来。
参考答案（家长）：必败态，因为轮到谁谁就输了。
参考答案（家长）：思想一样，只是运算换成了异或。