复杂度正确,不知为何跑的很慢,是代码原因还是语言特性啊qaq
顺便有没有大佬告诉我如何优雅的定义一个确定大小且里面的数都是 0 的列表啊,百度无果,只会定义后再写个循环赋值。
以下是代码:
n=0;mu=[];vis=[];pri=[];sum=[]
def init() :
mu[1]=1
for i in range(2,n+1,1) :
if(vis[i]==0) :
pri[0]+=1
pri[pri[0]]=i
mu[i]=-1
sum[i]=1
for j in range(1,pri[0]+1,1) :
k=pri[j]*i
if(k>n) :
break
vis[k]=1
if(i%pri[j]==0) :
sum[i*pri[j]]=mu[i]
mu[k]=0
break
else :
sum[i*pri[j]]=mu[i]-sum[i]
mu[k]=-mu[i]
for i in range(1,n+1,1) :
sum[i]+=sum[i-1]
n=int(input())
for i in range(0,n+1,1) :
mu.append(0)
vis.append(0)
sum.append(0)
pri.append(0)
init()
Ans=0
l=1
while(l<=n) :
r=int(n/int(n/l))
Ans+=int(sum[r]-sum[l-1])*int(n/l)*int(n/l)
l=r+1
print(Ans)