Luogu P3935 Calculating

Luogu P3935 Calculating"/>

Luogu P3935 Calculating

题目大意

给定 l , r l,r l,r，求 ∑ i = l r ∑ k ∣ i 1 \sum_{i=l}^r\sum_{k|i}1 i=l∑r​k∣i∑​1

数据范围　 1 ⩽ l , r ⩽ 1.6 × 1 0 14 3 second 1\leqslant l,r\leqslant 1.6\times 10^{14}\quad3\ \text{second} 1⩽l,r⩽1.6×10143 second

题解

可以发现， 原式等价于：
Sum d ( r ) − Sum d ( l − 1 ) \text{Sum}_{d}(r)-\text{Sum}_{d}(l-1) Sumd​(r)−Sumd​(l−1)其中 d d d 是约数个数函数。
某些学过杜教筛的（比如我）会开始考虑，然后发现打死都想不出来（至少我想不出来）……可能有的大佬想出来了，结果时间复杂度是 Θ ( n 2 3 ) \Theta(n^{\frac 23}) Θ(n32​)，发现死都卡不过去……好吧。
Sum d ( n ) = ∑ i = 1 n ∑ k ∣ i 1 = ∑ k = 1 n ∑ k ∣ i i ⩽ n 1 = ∑ k = 1 n ⌊ n k ⌋ \begin{aligned} \text{Sum}_{d}(n)&=\sum_{i=1}^n\sum_{k|i}1\\ &=\sum_{k=1}^n\sum_{k|i}^{i\leqslant n}1\\ &=\sum_{k=1}^n\Big\lfloor\frac nk \Big\rfloor\\ \end{aligned} Sumd​(n)​=i=1∑n​k∣i∑​1=k=1∑n​k∣i∑i⩽n​1=k=1∑n​⌊kn​⌋​

心情舒畅。除法分块，时间复杂度 Θ ( n ) \Theta(\sqrt n) Θ(n ​) 。

#include<bits/stdc++.h>
using namespace std;
#define mod 998244353
long long ds(long long n){long long ans=0;for(long long l=1,r;l<=n;l=r+1){r=n/(n/l); if(r>n) r=n;ans+=(n/l)*(r-l+1);ans=ans%mod;} return ans;
}
int main(void){long long l,r;scanf("%lld%lld",&l,&r);printf("%lld",(ds(r)-ds(l-1)+mod)%mod);return 0;
}