洛谷P3935 Calculating 题解

题目链接：P3935 Calculating

题意：

若 $n$ 的分解质因数结果为 $\prod_{i=1}^{s}p_i^{k_i}$

令 $f(n) = \prod_{i=1}^{s}(k_i+1)$

求

$$\sum\limits_{i=l}^{r}f(i) \bmod 998244353$$

根据容斥原理，可以把答案分为两个部分

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

然后推推柿子

$$\begin{aligned} \sum_{i=1}^{r}f(i) &= \sum_{i=1}^{r}\prod_{j=1}^{s_i}{(k_{ij}+1)} \\&=\sum_{i=1}^{r}\sum_{d\mid i}1 \\&=\sum_{i=1}^{r}\left\lfloor\dfrac{r}{i}\right\rfloor \end{aligned}$$

于是有

$$\sum_{i=1}^{n}f(i) = \sum_{i=1}^{n}\left\lfloor{\dfrac{n}{i}}\right\rfloor$$

考虑数论分块

时间复杂度 $O(\sqrt{r})$

代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod=998244353;
int L,R;
int solve(int n)
{
    int l=1,r=0,res=0;
    while(l<=n)
    {
        r=n/(n/l);
        res=(res+(r-l+1)*(n/l)%mod)%mod;
        l=r+1;
    }
    return res%mod;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> L >> R;
    cout << (solve(R)-solve(L-1)+mod)%mod << endl;
    return 0;
}