一些特殊的用法 trick

约数个数

在小于 \(10^5\) 的数中，一个数最多有128个因子。

在小于 \(10^5\) 的数中，一个数最多有 \(128\) 个因子。
在小于 \(10^6\) 的数中，一个数最多有 \(240\) 个因子。
在小于 \(10^7\) 的数中，一个数最多有 \(448\) 个因子。
在小于 \(10^8\) 的数中，一个数最多有 \(768\) 个因子。
在小于 \(10^9\) 的数中，一个数最多有 \(1344\) 个因子。
在小于 \(10^{10}\) 的数中，一个数最多有 \(2304\) 个因子。
在小于 \(10^{12}\) 的数中，一个数最多有 \(6720\) 个因子。
在小于 \(10^{15}\) 的数中，一个数最多有 \(26880\) 个因子。
在小于 \(10^{18}\) 的数中，一个数最多有 \(103680\) 个因子。

质数个数

\(1\sim n\) 中的质数个数约为：

\[\frac{x}{\ln x} \]

这就是一种启发，使用枚举质数来优化时间。

特殊的前 n 项和

\(\sqrt n\) 的前 n 项和

调和级数的前 n 项和

调和级数即：

\[\sum_i^n \frac{1}{i} \approx \ln n \]

即：

\[\sum_i^n \frac{n}{i} \approx n\ln n \]

常用于某些题时间的计算，比如这样：

for (int i = 1; i <= n; i ++ )
	for (int j = 1; j <= n / i; j ++ )
	{
		....
	}

这个时间复杂度不是 \(\operatorname O(n^2)\)，而是 \(\operatorname O(n\log n)\)。算是常识。

排列中 mex 与 min 的转化

对于一个排列，前缀 mex 的询问，可以转换为后缀最小值：

\[\operatorname{mex}_{i = 1}^ja_i = \min_{i = j + 1}^n \limits{a_i} \]

例题：Codeforces Round 915 (Div. 2) D. Cyclic MEX

计算 \(n!\) 的末尾 \(0\) 的个数

公式如下：

\[ans = \lfloor \frac{n}{5} \rfloor + \lfloor \frac{n}{25} \rfloor + \lfloor \frac{n}{125} \rfloor + ... \]

计算 \(n!\) 的末尾 \(0\) 的个数，实际上就是计算 \(1 * 2 * 3 * ... * n - 1 * n\) 中因子 \(10\) 的个数

\(10 = 2 * 5\) ，且在 \(n!\) 中，因子 \(2\) 的个数远远多于因子 \(5\) 的个数 ，所以只需要统计 \(n!\) 中所有因子 \(5\) 的个数即可

已知 \(1\) 到 \(n\) 中 \(5\) 的倍数的个数为 \(\lfloor \frac{n}{5} \rfloor\)，但如果直接将 \(\lfloor \frac{n}{5} \rfloor\) 当作答案会漏掉 \(5\) 的个数
因为 \(25 = 5 * 5\) 贡献了 \(2\) 个 \(5\) , \(125 = 5 * 5 * 5\) 贡献了 \(3\) 个 \(5\) ...

可以通过重复计数来补上这些漏掉的 \(5\)

• \(\lfloor \frac{n}{5} \rfloor\) 统计所有 \(5\) 的倍数贡献的第一个 \(5\)
• \(\lfloor \frac{n}{25} \rfloor\) 统计所有 \(25\) 的倍数贡献的第二个 \(5\)
• \(\lfloor \frac{n}{125} \rfloor\) 统计所有 \(125\) 的倍数贡献的第三个 \(5\)
• ......

这样一来就可以完整地统计出 \(n!\) 中所有因子 \(5\) 的个数了。

本质上这个算是利用特殊的因子来确定合数，用一个确定另一个，这种转化的思想很 nb。