洛谷P3935 Calculating 题解

题目链接：P3935 Calculating

题意：

若 n n n 的分解质因数结果为 ∏ i = 1 s p i k i prod_{i=1}^{s}p_i^{k_i} ∏i=1s​piki​​

令 f ( n ) = ∏ i = 1 s ( k i + 1 ) f(n) = prod_{i=1}^{s}(k_i+1) f(n)=∏i=1s​(ki​+1)

求
∑ i = l r f ( i )   m o d   998244353 sumlimits_{i=l}^{r}f(i) bmod 998244353 i=l∑r​f(i)mod998244353

根据容斥定理，可以把答案分为两个部分
∑ i = l r f ( i ) = ∑ i = 1 r f ( i ) − ∑ i = 1 l − 1 f ( i ) sum_{i=l}^{r}f(i) = sum_{i=1}^{r}f(i) - sum_{i=1}^{l-1}f(i) i=l∑r​f(i)=i=1∑r​f(i)−i=1∑l−1​f(i)
然后推推柿子
∑ i = 1 r f ( i ) = ∑ i = 1 r ∏ j = 1 s i ( k i j + 1 ) = ∑ i = 1 r ∑ d ∣ i 1 = ∑ i = 1 r ⌊ r 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_{dmid i}1 \&=sum_{i=1}^{r}leftlfloordfrac{r}{i}rightrfloor end{aligned} i=1∑r​f(i)​=i=1∑r​j=1∏si​​(kij​+1)=i=1∑r​d∣i∑​1=i=1∑r​⌊ir​⌋​
于是有
∑ i = 1 n f ( i ) = ∑ i = 1 n ⌊ n i ⌋ sum_{i=1}^{n}f(i) = sum_{i=1}^{n}leftlfloor{dfrac{n}{i}}rightrfloor i=1∑n​f(i)=i=1∑n​⌊in​⌋
考虑数论分块

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

代码如下

#include 
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;
}

转载请说明出处