题解 P3935 【Calculating】

· · 题解

块状链表块状数组分块，数论数学，期望，概率论,统计，素数判断质数筛法，莫比乌斯反演什么的我一个小学生看不懂啦~

首先要看懂这个f函数。根据小学奥数的“因数个数定理”不难看出f(x)就是求x的因数个数的。

这题给定的l,r，就是求l~r之间所有数因数个数之和。然后可以先求出1~r的因数个数和，1~(l-1)的因数个数和，最后相减。

如何求1~n的因数个数和？见代码。

#include<bits/stdc++.h>
#define ll long long
using namespace std; 
const ll mod=998244353;
ll cnt(ll n)
{
    ll sum=0;
    ll t=(ll)sqrt((double)n);
    //sqrt(n)
    for(ll i=1;i<=t;i++)
    {
        sum+=(n/i)%mod;
    }
    sum*=2;//对称性,最后*2就好了 
    sum=sum-t*t;//记得这里一定要减去多算的 
    sum=(sum%mod+mod)%mod;//注意负数 
    return sum;
}
int main() 
{
    ll l,r;
    scanf("%lld%lld",&l,&r);
    ll ans=cnt(r)-cnt(l-1);
    ans=(ans%mod+mod)%mod;//这边也要注意负数 
    printf("%lld\n",ans);
    return 0; 
}