提交时间:2022-08-03 18:25:04

运行 ID: 57096

#include<iostream> int n,st[10000001],pn[700000],cnt,sum,fs[10000001]={0,1},ans=1; void dfs(int v,int f,bool flag){ int now=v*f; if(flag) fs[now]=fs[v]*fs[f]; else{ int ins=now;fs[now]=1; for(int i=0;ins>=now/ins;i++){ int sum=0,pls=1,pfs=0; while(!(ins%pn[i])){ sum++; ins/=pn[i]; } for(int j=0;j<=sum;j++){ pfs+=pls; pls*=pn[i]; } fs[now]*=pfs; } if(ins>1) fs[now]*=ins; } ans+=fs[now]; for(int i=0;pn[i]*now<=n;i++){ if(pn[i]==f) dfs(now,pn[i],0); if(pn[i]>f) dfs(now,pn[i],1); } } int main(){ scanf("%d",&n); for(int i=2;i<=n;i++){ if(!st[i]){ pn[cnt++]=i; fs[i]=i+1; } for(int j=0;i*pn[j]<=n;j++){ st[i*pn[j]]=1; if(!(i%pn[j])) break; } } for(int i=0;i<cnt;i++) dfs(1,pn[i],1); printf("%d",ans); return 0; }