【BZOJ4176】Lucas的数论-杜教筛

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

求$$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}f(ij)$$，其中$f(x)$表示$x$的约数个数，$0\leq n\leq 10^9$，答案膜$10^9+7$

题解

首先有个妙不可言（被hjw污染了）的结论：$$f(nm)=\sum\limits_{i|n}\sum\limits_{j|m}[gcd(i,j)=1]$$

证明：咕

那么大力推一波式子：

$$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}f(ij)$$

$$=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\sum\limits_{a|i}\sum\limits_{b|j}[gcd(a,b)=1]$$

$$=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\sum\limits_{a|i}\sum\limits_{b|j}\sum\limits_{d|gcd(a,b)}\mu(d)$$

$$=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\sum\limits_{a|i}\sum\limits_{b|j}\sum\limits_{d|a\& d|b}\mu(d)$$

$$=\sum\limits_{d=1}^{n}\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{a=1}^{\lfloor\frac{n}{id}\rfloor}\sum\limits_{b=1}^{\lfloor\frac{n}{jd}\rfloor}\mu(d)$$

$$=\sum\limits_{d=1}^{n}\mu(d)(\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{n}{id}\rfloor)$$

杜教筛+莫比乌斯反演解决

时间复杂度：$O(n^{\frac{2}{3}}logn+n^{\frac{3}{4}})$

代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<map>
#define mod 1000000007
using namespace std;
typedef long long ll;
ll n,pri=,p[],miu[],pre[],ans=;
bool isp[];
map<ll,ll>HASH;
void _(){
miu[]=pre[]=;
for(int i=;i<=;i++){
if(!isp[i]){
p[++pri]=i;
miu[i]=-;
}
for(int j=;j<=pri&&i*p[j]<=;j++){
isp[i*p[j]]=true;
if(i%p[j]==){
miu[i*p[j]]=;
break;
}
miu[i*p[j]]=-miu[i];
}
}
for(int i=;i<=;i++){
pre[i]=(pre[i-]+miu[i]+mod)%mod;
}
}
ll work1(ll x){
if(x<=)return pre[x];
if(HASH.count(x))return HASH[x];
ll ret=;
for(int i=,j;i<=x;i=j+){
j=x/(x/i);
ret=(ret-(j-i+)*work1(x/i)%mod+mod)%mod;
}
HASH[x]=ret;
return ret;
}
ll work2(ll x){
ll ret=;
for(int i=,j;i<=x;i=j+){
j=x/(x/i);
ret=(ret+(x/i)*(j-i+))%mod;
}
return ret*ret%mod;
}
int main(){
_();
scanf("%lld",&n);
for(int i=,j;i<=n;i=j+){
j=n/(n/i);
ans=(ans+(work1(j)-work1(i-)+mod)%mod*work2(n/i))%mod;
}
printf("%lld",ans);
return ;
}