imicola 数学杂项trick
数学杂项trick

数学杂项trick

3,604 字 · 约 9 分钟

偏门/变态 Trick 秒杀清单

这份清单专门收录那些在算法竞赛中“见效极快、推导极难”的数学结论。遇到符合特征的题目,直接套公式即可。

一、 数论与代数“一击必杀”结论

1. 麦乐鸡定理 (买不到的数目 / Frobenius 币问题)

  • 题目特征:给定两个互质的正整数 aa 和 bb,问用这两个数通过非负整数次相加,最大不能组合出的数是多少?或者问共有多少个数不能被组合出?
  • 秒杀结论:
    • 最大不能组合出的数:a×b−a−ba \times b - a - b
    • 不能组合出的数的总个数:(a−1)(b−1)2\frac{(a-1)(b-1)}{2}
  • 陷阱:必须保证 gcd⁡(a,b)=1\gcd(a, b) = 1。如果 gcd⁡(a,b)>1\gcd(a, b) > 1,则不能组合出的数有无限个。

2. 互质和定理

  • 题目特征:求小于等于 NN 且与 NN 互质的所有数的和。
  • 秒杀结论:Sum=N×ϕ(N)2Sum = \frac{N \times \phi(N)}{2} (当 N>1N > 1 时)。ϕ(N)\phi(N) 是欧拉函数。

3. 威尔逊定理 (阶乘取模)

  • 题目特征:题目出现大数的阶乘对某个数取模,且形如 (P−1)!(modP)(P-1)! \pmod P。
  • 秒杀结论:当且仅当 PP 为质数时,(P−1)!≡−1(modP)(P-1)! \equiv -1 \pmod P (也就是 ≡P−1\equiv P-1)。
  • 衍生:如果问 (P−2)!(modP)(P-2)! \pmod P,结论是 11。

4. 勒让德定理 (阶乘质因子分解)

  • 题目特征:问 N!N! (NN 的阶乘)末尾有多少个零?或者问 N!N! 能被质数 pp 的最高多少次幂整除?
  • 秒杀结论:N!N! 中质因子 pp 的个数为 ∑k=1∞⌊Npk⌋\sum_{k=1}^{\infty} \lfloor \frac{N}{p^k} \rfloor。求末尾零的个数,就是求质因子 55 的个数(因为 22 的个数显然远多于 55)。

5. 平方和定理 (费马二平方和定理)

  • 题目特征:问一个整数能否表示为两个完全平方数之和 x2+y2x^2 + y^2。
  • 秒杀结论:一个数可以表示为两平方和,当且仅当其质因数分解中,所有形如 4k+34k+3 的质因子,其指数都为偶数。
  • 衍生:所有形如 4k+14k+1 的奇素数必定能唯一地写成两个平方数之和。

6. 平方差定理(两平方数之差)

  • 题目特征:问一个整数 nn 能否表示为两个完全平方数之差,即 x2−y2x^2-y^2;或者要求快速构造这两个平方数。
  • 秒杀结论:
    • 因为 x2−y2=(x−y)(x+y)x^2-y^2=(x-y)(x+y)
    • 一个正整数 nn 可以表示为两个平方数之差,当且仅当 n≢2(mod4)n \not\equiv 2 \pmod 4
    • 也就是说:
      • 若 nn 是奇数,一定可以表示
      • 若 nn 是 44 的倍数,一定可以表示
      • 若 n≡2(mod4)n \equiv 2 \pmod 4,一定不可以表示
  • 快速构造:
    • 若 nn 为奇数:
      n=(n+12)2−(n−12)2n=\left(\frac{n+1}{2}\right)^2-\left(\frac{n-1}{2}\right)^2
    • 若 nn 为 4k4k:
      n=(k+1)2−(k−1)2n=(k+1)^2-(k-1)^2
  • 陷阱:
    • 若题目要求 x,yx,y 为正整数,要额外检查构造出来的 yy 是否大于等于 11
    • n=0n=0 时有 02−02=00^2-0^2=0

7. 三平方和定理(Legendre 三平方定理)

  • 题目特征:问一个正整数能否表示为三个完全平方数之和。
  • 秒杀结论:
    • 一个正整数 nn 能表示为三个平方数之和,当且仅当
      n≠4a(8b+7)n \neq 4^a(8b+7)
  • 使用方法:
    • 不断把 nn 除以 44
    • 若最后剩下的数模 88 等于 77,则不能表示
    • 否则可以表示
  • 衍生:
    • 配合拉格朗日四平方和定理:任意正整数都能表示成至多四个平方数之和

8. 约数个数公式 / 约数和公式

  • 题目特征:求一个数的约数个数、所有约数之和、或者满足某些整除条件的方案数。
  • 前提:设
    n=p1a1p2a2⋯pkakn=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}
  • 秒杀结论:
    • 约数个数:
      d(n)=(a1+1)(a2+1)⋯(ak+1)d(n)=(a_1+1)(a_2+1)\cdots(a_k+1)
    • 约数和:
      σ(n)=∏i=1k(1+pi+pi2+⋯+piai)=∏i=1kpiai+1−1pi−1\sigma(n)=\prod_{i=1}^k (1+p_i+p_i^2+\cdots+p_i^{a_i}) =\prod_{i=1}^k \frac{p_i^{a_i+1}-1}{p_i-1}
  • 题目特征补充:
    • “有多少种乘法拆分”
    • “多少个因子满足某性质”
    • “枚举约数但数据很大”

9. 线性同余方程(扩展欧几里得)

  • 题目特征:求
    ax≡b(modm)ax \equiv b \pmod m
    是否有解,有多少解,或求最小正整数解。
  • 秒杀结论:
    • 设 d=gcd⁡(a,m)d=\gcd(a,m)
    • 方程有解当且仅当 d∣bd \mid b
    • 若有解,先把式子同时除以 dd:
      adx≡bd(modmd)\frac{a}{d}x \equiv \frac{b}{d} \pmod{\frac{m}{d}}
    • 此时 ad\frac{a}{d} 与 md\frac{m}{d} 互质,可用扩展欧几里得求逆元
  • 补充:
    • 模逆元存在当且仅当 gcd⁡(a,m)=1\gcd(a,m)=1
    • 若存在逆元,则
      x≡a−1b(modm)x \equiv a^{-1}b \pmod m

10. 中国剩余定理(CRT)

  • 题目特征:求一个数同时满足多个同余条件:
    x≡a1(modm1),x≡a2(modm2),…x\equiv a_1 \pmod{m_1},\quad x\equiv a_2 \pmod{m_2},\quad \dots
  • 秒杀结论:
    • 若各模数两两互质,则解在模 M=∏miM=\prod m_i 意义下唯一
    • 可直接套 CRT 合并
  • 实战思路:
    • 先求总模数 MM
    • 对每个方程设 Mi=M/miM_i=M/m_i
    • 求 MiM_i 在模 mim_i 下的逆元 tit_i
    • 则
      x≡∑aiMiti(modM)x \equiv \sum a_i M_i t_i \pmod M
  • 陷阱:
    • 若模数不互质,不能直接套标准 CRT,要判是否矛盾,再做扩展 CRT

二、 博弈论“玄学”模型

校赛最喜欢考博弈论结论题,除了 Nim,以下两个模型出场率极高且很难现场推导:

1. 威佐夫博弈 (Wythoff's Game) & 黄金分割比

  • 题目特征:有两堆石子,每次有两种操作:要么在其中一堆取任意数量,要么在两堆中取相同数量。最后取完者胜。
  • 秒杀结论:利用黄金分割率 ϕ=1+52\phi = \frac{1+\sqrt{5}}{2}。
    假设当前两堆石子数为 (x,y)(x, y) 且 x≤yx \le y,两堆的差值为 d=y−xd = y - x。
    如果 x==⌊d×ϕ⌋x == \lfloor d \times \phi \rfloor,则当前状态为必败态(先手必败)。否则先手必胜。

2. 斐波那契博弈 (Fibonacci Nim)

  • 题目特征:只有一堆石子,共 NN 个。先手第一次可以取任意多个,但不能全取完。之后每次每个人取的个数不能超过上个人取数的 2 倍。最后取完者胜。
  • 秒杀结论:当且仅当 NN 是斐波那契数时,先手必败。否则先手必胜。(基于 Zeckendorf 定理,任何正整数都能唯一表示为不相邻的斐波那契数之和)。

3. Nim 游戏 & 异或和定理

  • 题目特征:有若干堆石子,每次从某一堆取任意正数个,最后取完者胜。
  • 秒杀结论:
    • 设所有堆大小异或和为
      x=a1⊕a2⊕⋯⊕anx=a_1\oplus a_2\oplus \cdots \oplus a_n
    • 若 x=0x=0,则当前是必败态
    • 若 x≠0x\neq 0,则当前是必胜态
  • 经典操作:
    • 必胜时,总能找到一堆,把它变成某个更小值,使得修改后总异或和为 00

4. SG 函数(Sprague-Grundy)

  • 题目特征:复杂博弈拆成若干个独立子游戏,然后每步只操作其中一个子游戏。
  • 秒杀结论:
    • 每个状态有一个 SG 值
    • 多个独立子游戏的总 SG 值为所有子游戏 SG 值的异或和
    • 总异或和为 00 则必败,否则必胜
  • 定义:
    • 一个状态的 SG 值等于它所有后继状态 SG 值集合的 mex
  • 题感提示:
    • 看见“多个局面彼此独立”“每次只动一部分”,优先考虑 SG

三、 几何与离散图论 Trick

1. 皮克定理 (Pick's Theorem) - 格点多边形面积

  • 题目特征:给定一个顶点全在整点(坐标全为整数)上的多边形,求其面积、或者求多边形内部/边界的整点个数。
  • 秒杀结论:Area=I+B2−1Area = I + \frac{B}{2} - 1。
    其中 AreaArea 为多边形面积(可用叉积算),II 为多边形内部的整点数,BB 为多边形边界上的整点数。
    技巧:线段 (x1,y1)(x_1, y_1) 到 (x2,y2)(x_2, y_2) 上的整点个数为 gcd⁡(∣x1−x2∣,∣y1−y2∣)+1\gcd(|x_1-x_2|, |y_1-y_2|) + 1。边界整点总数 BB 就是各条边上整点数相加减去顶点数。

2. 欧拉公式 (平面图)

  • 题目特征:给出平面上若干点和不相交的线段(或求平面被划分成几块)。
  • 秒杀结论:对于任何连通的平面图,满足 V−E+F=2V - E + F = 2。
    (VV 是顶点数,EE 是边数,FF 是面数,包含最外部的无限面)。求划分区域数就是求 F−1=E−V+1F - 1 = E - V + 1。

四、 经典整数数列 (遇事不决先打表)

在校赛中,如果你推出前 5 项,发现符合下面数列特征,直接套公式,不需要证明。

1. 卡特兰数 (Catalan Number)

  • 前几项:1,1,2,5,14,42,132,429,1430…1, 1, 2, 5, 14, 42, 132, 429, 1430 \dots
  • 题目特征:
    • NN 对括号的合法匹配方案数。
    • NN 个节点构成的不同二叉树数量。
    • 凸 N+2N+2 边形划分为三角形的方案数。
    • 进出栈的合法序列数。
    • 在 N×NN \times N 网格中,从 (0,0)(0,0) 走到 (N,N)(N,N) 且不越过对角线的路径数。
  • 秒杀公式:Cn=(2nn)n+1=(2nn)−(2nn−1)C_n = \frac{\binom{2n}{n}}{n+1} = \binom{2n}{n} - \binom{2n}{n-1}。

2. 错排数 (Derangement)

  • 前几项:0,1,2,9,44,265,1854…0, 1, 2, 9, 44, 265, 1854 \dots
  • 题目特征:NN 个人抽 NN 份礼物,每个人都抽不到自己准备的礼物的方案数;NN 封信装错信封方案数。
  • 秒杀公式:
    • 递推:Dn=(n−1)×(Dn−1+Dn−2)D_n = (n-1) \times (D_{n-1} + D_{n-2})。
    • 通项近似:Dn=⌊n!e+0.5⌋D_n = \lfloor \frac{n!}{e} + 0.5 \rfloor (直接用阶乘除以自然常数 ee 四舍五入)。

3. 贝尔数 (Bell Number)

  • 前几项:1,1,2,5,15,52,203,877…1, 1, 2, 5, 15, 52, 203, 877 \dots
  • 题目特征:把 NN 个不同的元素划分成若干个(无序)非空集合的方案数。
  • 秒杀公式:没有简单的闭式,通常用第二类斯特林数求和 Bn=∑k=0nS(n,k)B_n = \sum_{k=0}^n S(n,k),或者使用贝尔三角形递推(类似杨辉三角,但 Ai,1=Ai−1,i−1A_{i,1} = A_{i-1, i-1},且 Ai,j=Ai−1,j−1+Ai,j−1A_{i,j} = A_{i-1, j-1} + A_{i, j-1})。
  • S(n,k)=1k!∑i=0k(−1)i(ki)(k−i)nS(n,k) = \frac{1}{k!} \sum_{i=0}^{k} (-1)^i \binom{k}{i} (k-i)^n

4. 第二类斯特林数(Stirling Number of the Second Kind)

  • 题目特征:把 nn 个不同元素划分成恰好 kk 个非空无序集合的方案数。
  • 秒杀结论:
    • 递推:
      S(n,k)=S(n−1,k−1)+k⋅S(n−1,k)S(n,k)=S(n-1,k-1)+k\cdot S(n-1,k)
  • 题感:
    • 最后一个元素单独成一组
    • 或加入已有的 kk 组之一
  • 和贝尔数关系:
    Bn=∑k=0nS(n,k)B_n=\sum_{k=0}^n S(n,k)

五、 期望与概率微操

1. 邮票收集问题 (Coupon Collector's Problem)

  • 题目特征:有 NN 种不同的卡片,每次买盲盒等概率获得其中一张,求收集齐所有 NN 种卡片期望购买的次数。
  • 秒杀结论:E=N×∑i=1N1iE = N \times \sum_{i=1}^N \frac{1}{i}。大约等于 Nln⁡N+γNN \ln N + \gamma N。

2. 随机游走期望

  • 题目特征:一条直线上有 0…N0 \dots N 个点。在位置 ii 时,有 pp 的概率走到 i+1i+1,有 1−p1-p 的概率走到 i−1i-1。求从 AA 走到 BB 的期望步数。
  • 秒杀结论:这通常是个一阶差分常系数线性递推方程。如果 p=0.5p = 0.5,从 00 走到 NN 的某一边界,期望经常是二次方级别的(例如从原点到距离 DD 的边界,期望步数是 D2D^2)。建议直接设未知数 EiE_i 然后解三对角矩阵(或者找规律)。

3. 容斥原理(至少一个 / 一个都没有)

  • 题目特征:计数中出现“至少一个满足”“一个都不满足”“恰好若干个满足”。
  • 秒杀结论:
    • 至少一个满足
      ∣∪Ai∣=∑∣Ai∣−∑∣Ai∩Aj∣+∑∣Ai∩Aj∩Ak∣−⋯|\cup A_i|=\sum |A_i|-\sum |A_i\cap A_j|+\sum |A_i\cap A_j\cap A_k|-\cdots
  • 经典模型:
    • 错排
    • 若干条件至少满足一个
    • 覆盖 / 禁止位置 / 染色限制
  • 技巧:
    • 看到“直接算很难,补集更简单”,优先考虑容斥

六、 组合恒等式秒杀

1. 前缀组合数求和

  • 题目特征:出现
    ∑k=0n(km)\sum_{k=0}^{n}\binom{k}{m}
    或相近形式。
  • 秒杀结论:
    ∑k=mn(km)=(n+1m+1)\sum_{k=m}^{n}\binom{k}{m}=\binom{n+1}{m+1}
  • 题感:
    • 连续若干项组合数求和,优先想“杨辉三角斜着加”

2. 范德蒙德卷积

  • 题目特征:出现双组合乘积求和:
    ∑k(nk)(mr−k)\sum_{k}\binom{n}{k}\binom{m}{r-k}
  • 秒杀结论:
    ∑k(nk)(mr−k)=(n+mr)\sum_{k}\binom{n}{k}\binom{m}{r-k}=\binom{n+m}{r}
  • 题感:
    • “从两组物品里总共选 rr 个”的计数,既可分类讨论,也可一步直选

七、 图论 / 结论型 Trick(补充)

1. 握手定理

  • 题目特征:无向图中点的度数、奇度点个数、边数之间关系。
  • 秒杀结论:
    • 所有点度数和等于边数的两倍:
      ∑deg(v)=2E\sum deg(v)=2E
    • 奇度点个数一定是偶数
  • 常见用途:
    • 判图是否可能存在
    • 构造反证
    • 欧拉路前置判断

2. 欧拉路 / 欧拉回路判定

  • 题目特征:要求一笔画、每条边恰好经过一次。
  • 秒杀结论(无向图):
    • 存在欧拉回路:所有非零度点连通,且所有点度数为偶数
    • 存在欧拉路但非回路:所有非零度点连通,且恰有两个奇度点
  • 题感:
    • “经过每条边一次”不是最短路,是欧拉路