(以下的除号皆表示整除)

用数论函数计算的时候,总会遇到这样一种问题:
$ \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) \cdot f(\frac{n}{l}) $。

结论是 $r = n / (n / l) + 1$ 。

证明:

  • 对于 l 设 $ n / l = x $
  • 那么由 $ n \; mod \; l = n – n / l \cdot l = n – l \cdot x $ 可知 $ n – l \cdot x \geq 0 $
  • 那么若 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 \leq n – k \cdot x < x $
  • 所以 $ n – k \cdot x = n \; mod \; x = n – n / x \cdot x $
  • 所以 $ k = n / x = n / (n / l) $
  • 由 k 的定义 $ n / k = n / l \; and \; 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<=i<r, \frac{n}{i} = \frac{n}{l} \& \frac{m}{i} = \frac{m}{l} $ 。

所以这样的区间的右端点为:$ r = min(n / (n / l), m / (m / l)) + 1 $ 。

所以还是可以一块一块的枚举求和。


发表评论

电子邮件地址不会被公开。 必填项已用*标注