洛谷P3935 约数个数定理，整除分块

题意：

设$x$的唯一分解为$x=p_1^{a_1}{p}_2^{a_2}...p_n^{a_n}$，令$f(x)=(a_1+1)(a_2+1)...(a_n+1)$，给出$l,r$，求
$$\sum _{i=l}^{r}f(i)$$

Solution：

先补一个结论

约数个数定理

记$x$的约数个数为$d(x)$

设唯一分解$x=p_1^{a_1}{p}_2^{a_2}...p_n^{a_n}$，那么每个因子的幂取值为$[0,a_i]$

所以约数就是幂的取值组合个数，即$d(x)=(a_1+1)(a_2+1)...(a_n+1)$

题目$f(x)=d(x)$，容斥即求
$$\sum _{i=1}^{r}d(i)-\sum _{i=1}^{l-1}d(i)$$
这是两个相同的问题，我们只需要考虑如何求解
$$\sum _{i=1}^{n}d(i)=\sum _{i=1}^n\sum _{d|i}1$$
右式意为，对一个$i$，找出他的所有因数个数，反过来考虑，我们可以考虑一个数，它存在多少个倍数$\le n$，于是即求
$$\sum _{i=1}^n\lfloor \frac{n}{i}\rfloor$$
整除分块即可，总复杂度$O(\sqrt{r})$

// #include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

using ll=long long;
const int N=1e5+5,inf=0x3fffffff;
const long long INF=0x3fffffffffffffff,mod=998244353;

ll f(ll x)
{
    ll ret=0;
    for(ll l=1,r;l<=x;l=r+1)
    {
        ll tmp=x/l; r=tmp?min(x/tmp,x):x;
        ret=(ret+(r-l+1)%mod*(tmp%mod)%mod)%mod;
    }
    return ret;
}

int main()
{
    ll l,r; cin>>l>>r;
    cout<<((f(r)-f(l-1))%mod+mod)%mod;  
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32