YOJ 102严神的数列

YOJ 102严神的数列

n<=3e6

#include using namespace std;int const N=4400000;int n,num,q[N],flag[N],x,e,ans,f[N],anss;void P(){ for(int i=2;i<=N;++i){ if(flag[i]) q[++num]=i; for(int j=1;j<=num;++j){ if(q[j]*i>N) break; flag[i*q[j]]=false; } }}int main(){// freopen("2.in","r",stdin);// freopen("2.out","w",stdout); scanf("%d",&n); num=0;memset(flag,true,sizeof flag);P(); memset(f,0,sizeof f); for(int i=1;i<=num;++i) f[q[i]]=1; ans=0; for(int i=2;i<=n;++i){ int x=i;e=1; anss=ans; while(1){ if(x%q[e]==0) x/=q[e],ans++; else e++; if(f[x]!=0){ans+=f[x];break;} if(x==1) break; } f[i]=ans-anss; } //for(int i=2;i<=n;++i) printf("%d:%d ",i,f[i]); printf("%d",ans); return 0; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。