【bzoj4176】Lucas的数论

  • 本文为博主原创,未经许可不得转载

利用上面那道题的结论就有:

$\sum_{i=1}^{n}\sum_{j=1}^{n}d(ij)=\sum_{i=1}^{n}\sum_{j=1}^{n}\left \lfloor \frac{n}{i} \right \rfloor \left \lfloor \frac{n}{j} \right \rfloor [gcd(i,j)==1]=\sum_{d=1}^{n}\mu(d) (\sum_{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor}\left \lfloor \frac{n}{di} \right \rfloor)^2$

莫比乌斯函数的前缀和杜教筛即可

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 1000100
#define cadd(a,b) a=add(a,b)
#define csub(a,b) a=sub(a,b)
#define cmul(a,b) a=mul(a,b)
using namespace std;
const int mod=1e9+7;
int n,N,cnt,ans,check[MAXN],prime[MAXN],mu[MAXN],vis[MAXN],value[MAXN];
inline int add(int a,int b){return (a+=b)>=mod?a-mod:a;}
inline int sub(int a,int b){return (a-=b)<0?a+mod:a;}
inline int mul(int a,int b){return 1LL*a*b%mod;}
inline int fac(int a){return mul(a,a);}
void Init(){
N=1000000; mu[1]=1;
for(int i=2;i<=N;++i){
if(!check[i]) prime[++cnt]=i,mu[i]=sub(0,1);
for(int j=1;j<=cnt&&prime[j]*i<=N;++j){
check[prime[j]*i]=1;
if(i%prime[j]==0) {mu[i*prime[j]]=0; break;}
else mu[i*prime[j]]=sub(0,mu[i]);
}
}
for(int i=1;i<=N;++i) cadd(mu[i],mu[i-1]);
}
int solve(int x){
int pos=n/x;
if(x<=N) return mu[x];
if(vis[pos]) return value[pos];
vis[pos]=1; value[pos]=1;
for(int i=2,last=0;i<=x;i=last+1){
last=x/(x/i);
csub(value[pos],mul(last-i+1,solve(x/i)));
}return value[pos];
}
int calc(int n){
int ret=0;
for(int i=1,last;i<=n;i=last+1){
last=n/(n/i);
cadd(ret,mul(last-i+1,(n/i)));
}return ret;
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
scanf("%d",&n); Init();
for(int i=1,last;i<=n;i=last+1){
last=n/(n/i);
cadd(ans,mul(sub(solve(last),solve(i-1)),fac(calc(n/i))));
}
printf("%d\n",ans);
return 0;
}
文章目录
,