C++11(clang++ 3.9) 解法, 执行用时: 229ms, 内存消耗: 21424K, 提交时间: 2019-03-15 14:30:32

#include<cstdio>
#define N 1000005
int b[N],i,j,n,t;bool w[N];long long a[N];
int main()
{
	scanf("%d",&n),a[1]=2;
	for(i=2;i<=n;a[i]*=i,i++)
	{
		if(!w[i])a[b[t++]=i]=i-1;
		for(j=0;i*b[j]<=n;j++)
		{
			w[i*b[j]]=true;
			if(i%b[j])a[i*b[j]]=a[i]*(b[j]-1);
			else{a[i*b[j]]=a[i]*b[j];break;}
		}
	}
	for(i=n;i;i--)for(j=i<<1;j<=n;j+=i)a[j]+=a[i];
	for(i=1;i<=n;i++)printf("%lld\n",a[i]>>1);
	return 0;
}

pypy3 解法, 执行用时: 1019ms, 内存消耗: 50428K, 提交时间: 2022-04-22 11:25:07

def ff(n):
    phi = list(range(n+1))
    ans = [1] * (n+1)
    for i in range(2, n+1):
        if phi[i] == i:
            for j in range(i, n+1, i):
                phi[j] -= phi[j] // i
        for j in range(i, n+1, i):
            ans[j] += phi[i] * i // 2
    return ans

n = int(input())

ans = ff(n)

for i in range(1, n+1):
    print(ans[i])