#includeusing namespace std; const int N=1e6+3; #define ll long long ll phi[N],f[N];int n; void getphi() { for(int i=1;i<=N;i++) phi[i]=i; for(int i=2;i<=N;i++) { if(phi[i]==i) { phi[i]=i; for(int j=i;j<=N;j+=i) { phi[j]=phi[j]*(i-1)/i; } } } return ; } void getans() { for(int i=1;i<=n;i++) { f[i]+=1;//1是任何数的约数,但是phi[1]*1/2=0;故需要+1 for(int j=i+i;j<=n;j+=i) { f[j]+=phi[j/i]*(ll)(j/i)/2; } } return ; } int main() { //freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); cin>>n; getphi();getans(); for(int i=1;i<=n;i++) { cout<
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)