一道推式子的数学题。
\[\begin{aligned}
\sum\limits_{i=l}^{r}\sum\limits_{j=1}^{i}\left\{\dfrac{j}{i}\right\}
&=\sum\limits_{i=l}^{r}\sum\limits_{j=1}^{i}\left(\dfrac{j}{i}-\left\lfloor\dfrac{j}{i}\right\rfloor\right)\\
&={\sum\limits_{i=l}^{r}\sum\limits_{j=1}^{i}}\dfrac{j}{i}-
{\sum\limits_{i=l}^{r}\sum\limits_{j=1}^{i}}\left\lfloor\dfrac{j}{i}\right\rfloor
\end{aligned}
\]
令 \(g(x)\) 为 \(1\) 到 \(x\) 的所有数的约数个数之和。即：\(\sum\limits_{i=1}^{x}\dfrac{x}{i}\)
则最终式子可以化简为：\(\sum\limits_{i=l}^{r}\left[i\cdot\left(\sum\limits_{j=1}^{i}j^{-1}\right)\right]-\sum\limits_{i=l}^{r}g(i)\)
第一项和第二项均可用两次前缀和预处理。
预处理 \(O(n\log n)\)，查询 \(O(1)\)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 5, N2 = 1e6 + 5, mod = 998244353;
ll T, s = 0, inv[N2], cnt[N2], x[N2], f[N2];
ll getans(ll n) {return (x[n] - f[n] + mod) % mod;}
int main() {
inv[1] = s = x[1] = f[1] = cnt[1] = 1;
for (ll i = 2; i <= 1e6; ++i) {
inv[i] = (mod - mod / i * inv[mod % i] % mod) % mod;
s = (s + inv[i]) % mod;
x[i] = (x[i - 1] + i * s) % mod;
}
for (ll i = 2; i <= 1e6; ++i) {
++cnt[i];
for (int j = i; j <= 1e6; j += i) ++cnt[j];
}
s = 0;
for (int i = 1; i <= 1e6; ++i) s = (s + cnt[i]) % mod, f[i] = (f[i - 1] + s) % mod;
scanf("%d", &T);
while (T--) {
ll p, q; scanf("%lld%lld", &p, &q);
printf("%lld\n", (getans(q) - getans(p - 1) + mod) % mod);
}
return 0;
}