题目概述
给出
n
，求 A=∑ni=1μ(i2),B=∑ni=1φ(i2) 。
解题报告
第一问……
i2
？喜闻乐见输出
1
。
第二问，由于 φ(i2)=iφ(i) ，所以要求
∑ni=1iφ(i)
（积性函数前缀和），那么我们就想到用杜教筛。xjb乱凑之后发现如果卷了
Id
，就可以得到：
S(n)=∑i=1ni2−∑i=2niS(⌊ni⌋)=n(n+1)(2n+1)6−∑i=2niS(⌊ni⌋)
然后就好了~
示例程序
#include<cstdio>
#include<map>
using namespace std;
typedef long long LL;
const int maxn=
1000000,MOD=
1e9+
7,INV2=(MOD+
1)/
2,INV6=(MOD+
1)/
6;
int n,p[maxn+
5],pre[maxn+
5];
bool pri[maxn+
5];
map<int,int> f;
inline void AMOD(
int &x,
int tem) {
if ((x+=tem)>=MOD) x-=MOD;}
inline void Make(){
pri[
0]=pri[
1]=
true;pre[
1]=
1;
for (
int i=
2;i<=maxn;i++){
if (!pri[i]) p[++p[
0]]=i,pre[i]=(LL)(i-
1)*i%MOD;
for (
int j=
1,t;j<=p[
0]&&(t=i*p[j])<=maxn;j++)
if (i%p[j]) pre[t]=(LL)pre[i]*pre[p[j]]%MOD,pri[t]=
true;
else {pre[t]=(LL)pre[i]*p[j]%MOD*p[j]%MOD;pri[t]=
true;
break;}
}
for (
int i=
2;i<=maxn;i++) AMOD(pre[i],pre[i-
1]);
}
int Solve(
int n){
if (n<=maxn)
return pre[n];
if (f.count(n))
return f[n];
int ans=(LL)n*(n+
1)%MOD*(n*
2+
1)%MOD*INV6%MOD;
for (
int l=
2,r;l<=n;l=r+
1){
r=n/(n/l);
int now=(LL)(l+r)*(r-l+
1)%MOD*INV2%MOD;
AMOD(ans,MOD-(LL)now*Solve(n/l)%MOD);
}
return f[n]=ans;
}
int main(){
scanf(
"%d",&n);
puts(
"1");Make();
return printf(
"%d\n",Solve(n)),
0;
}
