#整除分塊#洛谷 3935 Calculating

題目

求 [ l ∼ r ] [l\sim r] [l∼r]的約數個數和

分析

首先可以把它用字首和表示，那關鍵是怎麼實作呢？

設 f [ n ] f[n] f[n]為 [ 1 ∼ n ] [1\sim n] [1∼n]的約數個數和，那麼 f [ n ] = ∑ i = 1 n ⌊ n i ⌋ ( 轉 換 成 枚 舉 約 數 的 思 想 ) f[n]=\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor(轉換成枚舉約數的思想) f[n]=i=1∑n​⌊in​⌋(轉換成枚舉約數的思想)

那麼就可以用整除分塊求解

代碼

#include <cstdio>
#include <cctype>
#include <cstring>
#include <queue>
#define min(a,b) ((a)<(b)?(a):(b))
#define rr register
using namespace std;
typedef long long ll;
const ll mod=998244353;
inline ll iut(){
    rr ll ans=0; rr char c=getchar();
    while (!isdigit(c)) c=getchar();
    while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
    return ans;
}
inline signed mo(int x){return x>=mod?x-mod:x;}
inline signed answ(ll n){
    rr int ans=0;
    for (rr ll l=1,r;l<=n;l=r+1)
        r=n/(n/l),ans=mo(ans+(n/l)*(r-l+1)%mod);
    return ans;
}
signed main(){
    rr ll l=iut(),r=iut();
    return !printf("%d",mo(answ(r)-answ(l-1)+mod));
}