文章目录

题目分析代码

题目

[洛谷 P3935] Calculating

分析

$f(i)$ 是约数个数函数。 令 $g(n)={\sum }_{i=1}^{n}f(i)$，则 ${\sum }_{i=l}^{r}f(i)=g(r)-g(l-1)$。

$$\begin{array}{rl}g(n)=& \sum _{i=1}^n\sum _{j=1}^i[i\text{ mod }j=0]\\ =& \sum _{j=1}^n\lfloor \frac{n}{j}\rfloor \end{array}$$

整数分块： 对于 $i,n\in {\mathbb{N}}^{+}$，试找到一个最大的 $j\in {\mathbb{N}}^{+}$，使得 $\lfloor \frac{n}{i}\rfloor =\lfloor \frac{n}{j}\rfloor$。 可以证明，$j_{max}=\lfloor \frac{n}{\lfloor \frac{n}{i}\rfloor }\rfloor$。

证明： 设 $k=\lfloor \frac{n}{i}\rfloor =\lfloor \frac{n}{j}\rfloor$： $k=\lfloor \frac{n}{j}\rfloor ⟺k\le \frac{n}{j}<k+1⟺\frac{1}{k+1}<\frac{j}{n}\le \frac{1}{k}⟺\frac{n}{k}<j\le \frac{n}{k}$。 于是 $j_{max}=\lfloor \frac{n}{k}\rfloor =\lfloor \frac{n}{\lfloor \frac{n}{i}\rfloor }\rfloor$。

可以证明，对于任意 $n\in {\mathbb{N}}^{+}$，$\left|\left\{\lfloor \frac{n}{i}\rfloor \mid i\in {\mathbb{N}}^{+},i\le n\right\}\right|\le 2\lfloor \sqrt{n}\rfloor$。

证明： 显然 $\left|\left\{\lfloor \frac{n}{i}\rfloor \mid i\in {\mathbb{N}}^{+},i\le \sqrt{n}\right\}\right|\le \lfloor \sqrt{n}\rfloor$。 考虑 $\lfloor \frac{n}{i}\rfloor >\lfloor \sqrt{n}\rfloor$ 时： $\lfloor \frac{n}{i}\rfloor \le \lfloor \sqrt{n}\rfloor ⟹\lfloor \frac{n}{\lfloor \frac{n}{i}\rfloor }\rfloor \ge \sqrt{n}⟹\left|\left\{\lfloor \frac{n}{\lfloor \frac{n}{i}\rfloor }\rfloor \mid i\in {\mathbb{N}}^{+},i\le \sqrt{n}\right\}\right|\le \lfloor \sqrt{n}\rfloor ⟺\left|\left\{\lfloor \frac{n}{i}\rfloor \mid i\in {\mathbb{N}}^{+},i>\sqrt{n}\right\}\right|\le \lfloor \sqrt{n}\rfloor$。 于是 $\left|\left\{\lfloor \frac{n}{i}\rfloor \mid i\in {\mathbb{N}}^{+},i\le n\right\}\right|=\left|\left\{\lfloor \frac{n}{i}\rfloor \mid i\in {\mathbb{N}}^{+},i\le \sqrt{n}\right\}\right|+\left|\left\{\lfloor \frac{n}{i}\rfloor \mid i\in {\mathbb{N}}^{+},i>\sqrt{n}\right\}\right|\le 2\lfloor \sqrt{n}\rfloor$。

因此数论分块的时间复杂度 $O(\sqrt{n})$。

代码

#include <bits/stdc++.h> typedef long long LL; const int MOD = 998244353; LL Cal(LL N) { LL ret = 0; for (LL lft = 1, rgt = 1; lft <= N; lft = rgt + 1) { rgt = std::min(N / (N / lft), N); ret = (ret + (rgt - lft + 1) * (N / lft) % MOD) % MOD; } return ret; } int main() { LL L, R; scanf("%lld%lld", &L, &R); printf("%lld", ((Cal(R) - Cal(L - 1)) % MOD + MOD) % MOD); return 0; }