zcmimi's blog
avatar
zc
2020-03-19 19:22:00
  • 本文总阅读量
查看原题

点击跳转

x分解质因数结果为x=p_1^{k_1}p_2^{k_2}\cdots p_n^{k_n}

f(x)=(k_1+1)(k_2+1)\cdots (k_n+1)

f(x)其实就是d(x),x的约数个数

p_1^{k_1}的约数有1,p_1,p_1^2,\cdots,p_1^{k_1}

p_2^{k_2}的约数有1,p_2,p_2^2,\cdots,p_2^{k_2}

\cdots

p_n^{k_n}的约数有1,p_n,p_n^2,\cdots,p_n^{k_n}

根据乘法原理,d(x)=(k_1+1)(k_2+1)\cdots (k_n+1)

首先可以想到的是

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

那么

\sum_{i=1}^n f(i) \\ =\sum_{i=1}^n \sum_{j|i}1

换个枚举顺序

=\sum_{j=1}^n \sum_{j|i}1 \\ =\sum_{j=1}^n \left \lfloor \frac nj\right \rfloor

最后数论分块就可以了

#include<cstdio>
const int P=998244353;
typedef long long ll;
int calc(ll n){
    int res=0;
    for(ll l=1,r,i;l<=n;l=r+1){
        i=n/l;r=n/i;
        (res+=(r-l+1)*i%P)%=P;
    }
    return res;
}
int main(){
    ll l,r;scanf("%lld%lld",&l,&r);
    printf("%d\n",(calc(r)-calc(l-1)+P)%P);
}
LG 3935 Calculating
comment评论
Search
search