- Code:
- #include <cstdio>
- #include <algorithm>
- #define N 1000004
- #define setIO(s) freopen(s".in","r",stdin)
- using namespace std;
- int tot;
- int f[N],prime[N],vis[N],sum[N];
- int main()
- {
- //setIO("input");
- int n,i,j;
- scanf("%d",&n);
- sum[1]=f[1]=1;
- for(i=2;i<=n;++i)
- {
- if(!vis[i]) prime[++tot]=i,f[i]=2;
- for(j=1;j<=tot&&1ll*i*prime[j]<=1ll*n;++j)
- {
- vis[i*prime[j]]=1;
- if(i%prime[j]==0)
- {
- int h=i;
- for(;h%prime[j]==0;h/=prime[j]);
- f[i*prime[j]]=f[h]+f[i];
- break;
- }
- else
- {
- f[i*prime[j]]=f[i]*f[prime[j]];
- }
- }
- sum[i]=sum[i-1]+f[i];
- }
- printf("%d\n",sum[n]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3189668.html