P3935 Calculating
显然，$f(x)$ 表示 $x$ 的约数个数，即
$$
\sum _ {i = l} ^ r f(i) = \sum _ {i = l} ^ r \sum _ {j = 1} ^ i [j | i] \\
$$
计算
$$
\begin {aligned}
\sum _ {i = 1} ^ n f(i) &= \sum _ {i = 1} ^ n \sum _ {j = 1} ^ i [j | i] \\
&= \sum _ {j = 1} ^ n \left \lfloor \frac n j \right \rfloor
\end{aligned}
$$
数论分块即可。
查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include <cstdio>
using namespace std;
typedef long long LL;
const LL mod = 998244353;
LL f(LL k)
{
LL res = 0;
for (LL l = 1, r; l <= k; l = r + 1)
{
r = k / (k / l);
res = (res + (r - l + 1) * (k / l)) % mod;
}
return res;
}
int main()
{
LL l, r;
scanf("%lld%lld", &l, &r);
printf("%lld", (f(r) - f(l - 1) + mod) % mod);
return 0;
}
|