洛谷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;
}