正题
求 n n n 以内所有正整数的最大平方因子的和。答案对 2 64 2^{64} 264取模。
tips: x x x 是 y y y 的平方因子，当且仅当 x x x 是 y y y 的因子且 x \sqrt x x 恰为整数。
显然设
F
(
x
)
F(x)
F(x)为x的最大平方因子。
容易发现
F
(
x
)
F(x)
F(x)是一个积性函数，且
F
(
p
k
)
=
p
k
−
(
k
m
o
d
2
)
F(p^k)=p^{k-(k\mod 2)}
F(pk)=pk−(kmod2)
既然是求一个积性函数的前缀和，自然就想到了使用杜教筛或者
m
i
n
_
25
min\_{25}
min_25筛来求解，很遗憾不能通过此题。
还有一种新方法是powerful number，它能在快速计算构造函数G的前缀和的情况下，用
O
(
n
)
O(\sqrt n)
O(n
)的时间算出前缀和。可以先参考我这一篇Blog
这题则可以构造
G
(
x
)
=
1
,
H
∗
G
=
F
G(x)=1,H*G=F
G(x)=1,H∗G=F
则答案为
∑
i
=
1
n
H
(
i
)
(
n
/
i
)
\sum_{i=1}^n H(i)(n/i)
∑i=1nH(i)(n/i)
如果我们暴力枚举出每一个powerful number并进行求解，那么时间复杂度是
O
(
T
n
)
O(T\sqrt n)
O(Tn
)的，依然不能通过此题。
我们尝试找规律？
由于
H
=
F
/
G
H=F/G
H=F/G,且这个G是一个常值函数1，所以H是一个积性函数且在质数的指数幂上是F的差分。
为什么这么说，举个例子
F
(
p
k
)
=
∑
i
=
0
k
G
(
p
i
)
H
(
p
k
−
i
)
=
∑
i
=
0
k
H
(
p
i
)
F(p^k)=\sum_{i=0}^k G(p^i)H(p^{k-i})=\sum_{i=0}^k H(p^i)
F(pk)=∑i=0kG(pi)H(pk−i)=∑i=0kH(pi)，所以
F
F
F在质数的指数幂上是
H
H
H的前缀和，而
H
H
H则是
F
F
F的差分。
所以可以轻松得到
H
(
p
2
k
)
=
p
2
k
−
2
(
p
2
−
1
)
,
H
(
p
2
k
+
1
)
=
0
H(p^{2k})=p^{2k-2}(p^2-1),H(p^{2k+1})=0
H(p2k)=p2k−2(p2−1),H(p2k+1)=0
哦！
所以
H
H
H只有在完全平方数有值，那么式子就更简单了：
∑
i
=
1
n
H
(
i
2
)
⌊
n
i
2
⌋
\sum_{i=1}^{\sqrt n}H(i^2)\lfloor \frac{n}{i^2}\rfloor
∑i=1n
H(i2)⌊i2n⌋
用平凡的整除分块写一写，发现时间复杂度好像不对，却发现过了？
原因就在于后面的这个分块对象，可以帮助我们将时间复杂度降到
O
(
n
1
/
3
)
O(n^{1/3})
O(n1/3)。
分类讨论一下就可：
当
i
2
<
=
n
2
/
3
i^2<=n^{2/3}
i2<=n2/3时，
i
<
=
n
1
/
3
i<=n^{1/3}
i<=n1/3，这部分只需要
O
(
n
1
/
3
)
O(n^{1/3})
O(n1/3)就可以完成。
当
i
2
>
n
2
/
3
时
i^2>n^{2/3}时
i2>n2/3时，
⌊
n
i
2
⌋
<
=
n
1
/
3
\lfloor \frac n {i^2}\rfloor<=n^{1/3}
⌊i2n⌋<=n1/3，这部分也只需要
O
(
n
1
/
3
)
O(n^{1/3})
O(n1/3)就可以完成，另外，听说求sqrt时间复杂度为
O
(
1
)
O(1)
O(1)
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int N=10000010;
int T,p[N];
long long n;
bool vis[N];
ull h[N];
int main(){
scanf("%d",&T);
n=10000000;h[1]=1;
for(int i=2;i<=n;i++){
if(!vis[i]) p[++p[0]]=i,h[i]=1ll*i*i-1;
for(int j=1;j<=p[0] && i*p[j]<=n;j++){
vis[i*p[j]]=true;
if(i%p[j]==0) {h[i*p[j]]=h[i]*p[j]*p[j];break;}
h[i*p[j]]=h[i]*h[p[j]];
}
}
for(int i=2;i<=n;i++) h[i]+=h[i-1];
while(T--){
scanf("%lld",&n);
int l=1,r=0;
ull ans=0;
while(1ll*l*l<=n){
r=sqrtl(n/(n/l/l));
ans+=(h[r]-h[l-1])*(n/l/l);
l=r+1;
}
printf("%llu\n",ans);
}
}