信奥数学知识点概述
本次题目覆盖信息学竞赛核心数学内容，以数论为主，辅以组合数学与概率期望，聚焦竞赛高频考点，整体可分为六大模块：
一、数论基础：质数、约数、唯一分解
- 质数判定与筛法
- 试除法判断质数：循环边界、防溢出条件、偶数特判优化
- 埃氏筛法：原理、时间复杂度、标记合数方式
- 欧拉筛（线性筛）：核心思想——每个合数仅被最小质因子筛除
- 约数相关
- 试除法枚举约数、约数对收集方式
- 约数个数公式、约数和公式（基于质因数分解）
- $10^9$ 范围内整数的最大约数个数
- 唯一分解定理
- 正整数标准质因数分解形式：$n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$
- $n=1$ 的特殊定义与处理
二、GCD、LCM 与扩展欧几里得
- 最大公约数与最小公倍数
- 辗转相除法求 $\gcd(a,b)$ 及其时间复杂度
- $\operatorname{lcm}(a,b)$ 计算方式与防溢出写法
- 恒等式：$\gcd(a,b) \times \operatorname{lcm}(a,b) = a \times b$
- 裴蜀定理与扩展欧几里得
- 不定方程 $ax+by=c$ 有解的充要条件
- 裴蜀定理核心结论
- 扩展欧几里得算法求解方程整数解
三、同余、欧拉函数、逆元与 CRT
- 同余与模运算
- 同余基本性质：若 $a \equiv b \pmod{m}$，则运算保持同余
- 费马小定理适用条件、指数降幂应用
- 欧拉函数 $\varphi(n)$
- 定义、计算方式、常用结论
- 积性性质辨析
- 乘法逆元
- 逆元定义：$b \times \operatorname{inv}(b) \equiv 1 \pmod{p}$
- 费马小定理求逆元：$\operatorname{inv}(b) = b^{p-2} \bmod p$
- 线性递推求 $1\sim n$ 逆元公式
- 中国剩余定理
- 经典 CRT：模数两两互质要求
- 扩展 CRT：支持模数不互质，核心改进点
四、进阶数论：整除分块与卢卡斯定理
- 整除分块
- 求解 $\displaystyle\sum_{i=1}^n \left\lfloor \frac{n}{i} \right\rfloor$ 的时间复杂度
- 分块右端点计算公式：$r = \left\lfloor \frac{n}{\left\lfloor \frac{n}{l} \right\rfloor} \right\rfloor$
- 卢卡斯定理
- 组合数取模公式：$\displaystyle\binom{n}{m} \bmod p$
- 适用条件与典型应用场景
- 大 $n$ 小 $m$ 组合数计算方式
五、组合数学
- 基础组合与排列
- 组合数递推公式：$\displaystyle\binom{n}{m} = \binom{n-1}{m-1} + \binom{n-1}{m}$
- 二项式定理：$(x+y)^n$ 中 $x^k y^{n-k}$ 系数为 $\displaystyle\binom{n}{k}$
- 隔板法：相同球放不同盒子（至少1个 / 允许空盒）
- 不定方程 $x_1+x_2+\cdots+x_k=n$ 非负整数解计数
- 特殊排列与计数
- 错位排列：递推式 $D(n) = (n-1)(D(n-1)+D(n-2))$、初始条件、$D_5$ 数值
- 不同球放相同盒子（非空）计数
- 斯特林数与卡特兰数
- 第一类、第二类斯特林数本质区别
- 卡特兰数通项：$\displaystyle C_n = \frac{1}{n+1}\binom{2n}{n}$、递推式、$C_4$ 数值
- 容斥原理
- 三集合并集公式： $$ |A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C| $$
- 求“至少一个满足”类问题的转化技巧
- 容斥求 $1\sim n$ 中被若干数整除的数的个数
六、概率与期望
- 期望线性性质：$E(aX + bY) = aE(X) + bE(Y)$ 及成立条件
- 期望 DP 基础状态定义
- 带环期望 DP 的核心处理思想
—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com
