[hdu6134]Battlestation Operational

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define mod 1000000007
 4 #define N 1000005
 5 long long n,ans,mu[N],f[N],t[N],vis[N],p[N];
 6 void xxs(int n){
 7     mu[1]=f[1]=1;
 8     for(int i=2;i<=n;i++){
 9         if (!vis[i]){
10             p[++p[0]]=i;
11             mu[i]=-1;
12             t[i]=1;
13             f[i]=2;
14         }
15         for(int j=1;(j<=p[0])&&(i*p[j]<=n);j++){
16             vis[i*p[j]]=1;
17             if (i%p[j]==0){
18                 t[i*p[j]]=t[i]+1;
19                 f[i*p[j]]=f[i]/(t[i]+1)*(t[i]+2);
20                 break;
21             }
22             t[i*p[j]]=1;
23             f[i*p[j]]=f[i]*2;
24             mu[i*p[j]]=-mu[i];
25         }
26     }
27     t[1]=1;
28     for(int i=2;i<=n;i++){
29         t[i]=(f[i-1]+t[i-1]+1)%mod;
30         mu[i]+=mu[i-1];
31     }
32     for(int i=2;i<=n;i++)f[i]=(t[i]+f[i-1])%mod;
33 }
34 int main(){
35     xxs(N-5);
36     while (scanf("%lld",&n)!=EOF){
37         ans=0;
38         for(int i=1,j;i<=n;i=j+1){
39             j=n/(n/i);
40             ans=(ans+(mu[j]-mu[i-1]+mod)%mod*f[n/i])%mod;
41         }
42         printf("%lld\n",ans);
43     }
44 }
View Code