数学建模
本节目标
识别隐藏数学关系，用最小充分状态连接二分、哈希与多指针。
识别信号
题面给出平方、阶乘、分数或只含少数质因子的生成规则，却没有直接给出数据结构时，先问：答案真正由哪条数学关系决定？本栏的入口不是固定算法，而是把关系翻译成可计算的边界、状态或生成过程。
核心定义与不变量
平方根中“答案不超过 x”是单调谓词；阶乘末尾零等于质因数 5 的总指数；分数的小数部分由余数唯一决定；丑数序列是从 1 开始、不断乘 2、3、5 的有序闭包。它们的最小充分信息分别是边界、计数、余数和三个生成指针。
朴素方法与瓶颈
逐个试平方、真的计算阶乘、无限模拟除法或把候选整数逐一判丑数，都会重复大量无关计算。数学关系让我们跳过中间对象：二分直接收缩答案，整除直接累计指数，哈希表记住余数位置，指针只产生下一个可能答案。
推导与实现框架
先写出隐藏关系，再挑最小状态，最后复用已有算法。单调边界复用第三章二分；“是否出现过这个余数”复用第二章哈希；多个有序候选的归并复用第四章多指针。实现时让状态更新严格对应推导，而不要把题目误当成公式记忆。
复杂度与数值边界
二分为 O(log x)；零的统计为 O(log_5 n)；分数的状态数不超过分母量级；丑数使用 O(n) 时间和空间。平方比较用除法避开乘法溢出；分数先提升到 64 位再取绝对值；丑数的候选乘积也要用更宽整数计算。
母题序列
常见误区
- 只看到“平方”就计算
mid * mid，忽略整型溢出。 - 只统计
n / 5，遗漏25、125提供的额外因子。 - 只记录已经写出的数字，而不记录余数首次出现的位置。
- 丑数候选相等时只移动一个指针，导致重复值。
迁移方向
遇到单调可行性，回到二分边界；状态能唯一决定后续时，考虑状态记忆；多个递增候选要合并且去重时，考虑多指针。更复杂的数论工具、完整动态规划分类不由本栏展开。