整除分块
（以下的除号皆表示整除）
用数论函数计算的时候，总会遇到这样一种问题： \(\sum_{i=1}^n f(\frac{n}{i})\) 。 \(O(n)\) 求往往无法满足需要。
但是打表可以发现， n/i 的取值对于一段连续的 i 是一致的，
那么可以考虑一块一块求。
设已知当前块的左端点为 l ，如果知道右端点 r（左闭右开），意味着 \(\forall l<=i<r, \frac{n}{i} = \frac{n}{l}\) ， 这一块对答案的贡献就是 \((r-l) \times f(\frac{n}{l})\) 。
结论是 \(r = n / (n / l) + 1\) 。
证明：
- 对于 l 设 \(n / l = x\)
- 那么由 \(n \bmod l = n - n / l \cdot l = n - l \cdot x\) 可知 $ n - l x $
- 那么若 \(l + 1\) 满足 \(n / (l + 1) = n / l\) ，可知也有 \(n - (l + 1) \cdot x \geq 0\)
- 即 \(n - l \cdot x \geq x\)
- 对于 k 若 \(n / k = n / l\) 而 \(n / (k + 1) != n / l\)
- 那么根据上式可得 k 满足 $ 0 n - k x < x$
- 所以 \(n - k \cdot x = n \bmod x = n - n / x \cdot x\)
- 所以 \(k = n / x = n / (n / l)\)
- 由 k 的定义 \(n / k = n / l \& n / (k + 1) != n / l\) 可知 k+1 即是要求的 r
那么可以枚举块，当前 l,r 可以求得，下一个块的 l 显然是当前 r。
有时候会有点变化：
要求 \(\sum_{i=1}^{min(n, m)} f(\frac{n}{i}) \cdot f(\frac{m}{i})\) 。
还是会存在 \(\forall l \le i < r, \frac{n}{i} = \frac{n}{l} \& \frac{m}{i} = \frac{m}{l}\) 。
所以这样的区间的右端点为：\(r = min(n / (n / l), m / (m / l)) + 1\) 。
所以还是可以一块一块的枚举求和。