洛谷 P3935 Calculating

题解

整除分块的裸题，整除分块用于求解 \(\sum_{i=1}^{n}\lfloor\frac{n}{i}\rfloor\)

\(f_x = (k_1+1)(k_2+1)⋯(k_n+1)\) 表示 \(x\) 的因子的个数。

\(\sum_{i=1}^{n} f_x\) 表示区间 \([1,n]\) 所有的数的因子的个数。

可以进一步求 \([1,n]\) 这个区间每个因子出现的次数，

例如：因子\(x\) 出现的次数为 \(\lfloor\frac{n}{x}\rfloor\) ，进而为 \(\sum_{i=1}^{n}\lfloor\frac{n}{i}\rfloor\)

\(\sum_{i=l}^{r} f_x =\sum_{i=1}^{r} f_x - \sum_{i=1}^{l-1} f_x\)

\(\sum_{i=l}^{r} f_x =\sum_{i=1}^{r}\lfloor\frac{r}{i}\rfloor - \sum_{i=1}^{l-1}\lfloor\frac{l-1}{i}\rfloor\)

代码

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
int main(){
    ll a,b,cnt=0;
    cin>>a>>b;
    for(ll l=1,r;l<=b;l=r+1){
        r=b/(b/l);
        cnt+=(r-l+1)*(b/l);
        cnt%=mod;
    }
    --a;
    for(ll l=1,r;l<=a;l=r+1){
        r=a/(a/l);
        cnt-=(r-l+1)*(a/l);
        cnt=(cnt%mod+mod)%mod;
    }
    cout<<(cnt%mod+mod)%mod<<endl;
    return 0;
}