HDU 6134 Battlestation Operational（莫比乌斯反演）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6134
题目大意：给定正整数
n
n
n ，求
∑
i
=
1
n
∑
j
=
1
i
⌈
i
j
⌉
[
gcd
(
i
,
j
)
=
1
]
(
1
≤
n
≤
1
e
6
)
\sum\limits_{i=1}^n\sum\limits_{j=1}^i\lceil\frac{i}{j}\rceil[\gcd(i,j)=1](1\leq n\leq 1e6)
i=1∑nj=1∑i⌈ji⌉[gcd(i,j)=1](1≤n≤1e6) ，其中
⌈
x
⌉
\lceil x\rceil
⌈x⌉ 为上取整符号。
题解：先转化一下式子：
⇒ ∑ i = 1 n ∑ j = 1 i ⌈ i j ⌉ ε ( gcd ( i , j ) ) \Rightarrow\sum\limits_{i=1}^n\sum\limits_{j=1}^i\lceil\frac{i}{j}\rceil\varepsilon(\gcd(i,j)) ⇒i=1∑nj=1∑i⌈ji⌉ε(gcd(i,j))
= ∑ i = 1 n ∑ j = 1 i ⌈ i j ⌉ ∑ t ∣ i , t ∣ j μ ( t ) =\sum\limits_{i=1}^n\sum\limits_{j=1}^i\lceil\frac{i}{j}\rceil\sum\limits_{t\mid i,t\mid j}\mu(t) =i=1∑nj=1∑i⌈ji⌉t∣i,t∣j∑μ(t)
= ∑ t = 1 n μ ( t ) ∑ i = 1 ⌊ n t ⌋ ∑ j = 1 i ⌈ i j ⌉ =\sum\limits_{t=1}^{n}\mu(t)\sum\limits_{i=1}^{\lfloor\frac{n}{t}\rfloor}\sum\limits_{j=1}^i\lceil\frac{i}{j}\rceil =t=1∑nμ(t)i=1∑⌊tn⌋j=1∑i⌈ji⌉
考虑上取整的意义，当 j ∣ i j\mid i j∣i 时， ⌈ i j ⌉ = ⌊ i j ⌋ \lceil\frac{i}{j}\rceil=\lfloor\frac{i}{j}\rfloor ⌈ji⌉=⌊ji⌋ ，反之当 j ∤ i j\nmid i j∤i 时，有 ⌈ i j ⌉ = ⌊ i j ⌋ + 1 \lceil\frac{i}{j}\rceil=\lfloor\frac{i}{j}\rfloor+1 ⌈ji⌉=⌊ji⌋+1 。那么式子可以继续转化一下：
⇒
∑
t
=
1
n
μ
(
t
)
∑
i
=
1
⌊
n
t
⌋
∑
j
=
1
i
(
⌊
i
j
⌋
+
[
j
∤
i
]
)
\Rightarrow\sum\limits_{t=1}^{n}\mu(t)\sum\limits_{i=1}^{\lfloor\frac{n}{t}\rfloor}\sum\limits_{j=1}^i(\lfloor\frac{i}{j}\rfloor+[j\nmid i])
⇒t=1∑nμ(t)i=1∑⌊tn⌋j=1∑i(⌊ji⌋+[j∤i])
=
∑
t
=
1
n
μ
(
t
)
∑
i
=
1
⌊
n
t
⌋
(
i
−
τ
(
i
)
+
∑
j
=
1
i
⌊
i
j
⌋
)
=\sum\limits_{t=1}^{n}\mu(t)\sum\limits_{i=1}^{\lfloor\frac{n}{t}\rfloor}(i-\tau(i)+\sum\limits_{j=1}^i \lfloor\frac{i}{j}\rfloor)
=t=1∑nμ(t)i=1∑⌊tn⌋(i−τ(i)+j=1∑i⌊ji⌋)
其中
τ
(
n
)
\tau(n)
τ(n) 为约数个数函数，且
τ
(
i
)
\tau (i)
τ(i) 是可以线性筛预处理的。那么我们只要处理
∑
i
=
1
⌊
n
t
⌋
∑
j
=
1
i
⌊
i
j
⌋
\sum\limits_{i=1}^{\lfloor\frac{n}{t}\rfloor}\sum\limits_{j=1}^i \lfloor\frac{i}{j}\rfloor
i=1∑⌊tn⌋j=1∑i⌊ji⌋ 这一部分即可。再考虑下取整的意义，不难发现，对于
∀
k
∈
Z
+
,
⌊
k
j
j
⌋
=
⌊
k
j
+
1
j
⌋
=
⌊
k
j
+
2
j
⌋
=
⋯
=
⌊
(
k
+
1
)
j
−
1
j
⌋
\forall k \in \mathbb{Z^{+}},\lfloor\frac{kj}{j}\rfloor=\lfloor\frac{kj+1}{j}\rfloor=\lfloor\frac{kj+2}{j}\rfloor=\cdots=\lfloor\frac{(k+1)j-1}{j}\rfloor
∀k∈Z+,⌊jkj⌋=⌊jkj+1⌋=⌊jkj+2⌋=⋯=⌊j(k+1)j−1⌋ ，那么对于区间
[
k
j
,
(
k
+
1
)
j
−
1
]
[kj,(k+1)j-1]
[kj,(k+1)j−1] ，同时加上值
k
k
k 即可。这里存在区间修改的问题，那么我们使用差分的技巧在原始的埃式筛中处理，再作两次前缀和即可，此时预处理复杂度为
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn) 。
最后用数论分块处理就行。
#include<bits/stdc++.h>
using namespace std;
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<":"<<x<<" "<<#y<<":"<<y<<endl
#define debug3(x,y,z) cerr<<#x<<":"<<x<<" "<<#y<<":"<<y<<" "<<#z<<":"<<z<<endl
typedef long long ll;
const int MAX=1e6+5;
const ll M=1e9+7;
int cnt=0;
int D[MAX],S[MAX],SS[MAX],tao[MAX],minp_v[MAX],part[MAX],prime[MAX],ST[MAX],mu[MAX],SM[MAX];
void pre(){
SM[0]=mu[0]=ST[0]=tao[0]=D[0]=S[0]=SS[0]=0;
memset(D,0,sizeof(D));
memset(mu,0,sizeof(D));
for(int j=1;j<MAX;++j){
for(int i=1;i*j<MAX;++i){
int l=i*j,r=(i+1)*j;
D[l]+=i;
if(r<MAX) D[r]-=i;
}
}
for(int i=1;i<MAX;++i) S[i]=(S[i-1]+D[i])%M;
SS[1]=S[1];
tao[1]=SM[1]=mu[1]=1;
ST[1]=0;
for(int i=2;i<MAX;++i){
if(!part[i]){
part[i]=i;
prime[cnt++]=i;
minp_v[i]=tao[i]=2;
mu[i]=-1;
}
SS[i]=((ll)SS[i-1]+(ll)S[i])%M;
ST[i]=((ll)ST[i-1]+(ll)i-(ll)tao[i])%M;
SM[i]=((ll)SM[i-1]+(ll)mu[i])%M;
for(int j=0;i*prime[j]<MAX;++j){
part[i*prime[j]]=prime[j];
if(i%prime[j]){
tao[i*prime[j]]=tao[i]*tao[prime[j]];
minp_v[i*prime[j]]=2;
mu[i*prime[j]]=-mu[i];
}
else{
tao[i*prime[j]]=tao[i]/minp_v[i];
minp_v[i*prime[j]]=minp_v[i]+1;
tao[i*prime[j]]*=minp_v[i*prime[j]];
break;
}
}
}
}
int main(){
pre();
int n;
while(cin>>n){
ll res=0;
for(ll l=1,r;l<=n;l=r+1){
r=n/(n/l);
res=(res+((ll)SM[r]-(ll)SM[l-1])%M*(((ll)ST[n/l]+(ll)SS[n/l])%M)%M)%M;
}
if(res<0) res+=M;
cout<<res<<endl;
}
}
意外的，时间并没有超过1秒（题目给了3秒）。