题解 P3935 Calculating

题面
首先题目给的柿子实际上就是$n$的因子个数
$[l,r]$运用前缀和拆成$[1,r]-[1,l-1]$

$$\sum_{i=1}^n\sum_{d|i}1$$ $$= \sum_{d=1}^n\sum_{d|i,i<=n}1$$ $$= \sum_{d=1}^n\lfloor\frac nd\rfloor$$

数论分块

// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
inline int work(ll x) {
    int ans = 0;
    for(ll l = 1, r; l <= x; l = r + 1) {
        r = x / (x / l);
        ans = (ans + 1ll * (r - l + 1) * (x / l)) % mod;
    }
    return ans;
}
int main() {
    ll l, r;
    scanf("%lld%lld", &l, &r);
    return printf("%lld\n", (work(r) - work(l - 1) + mod) % mod), 0;
}