HDU-6134 (莫比乌斯反演)

HDU-6134 Battlestation Operational

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+6;
const int p=1e9+7;
typedef long long ll;
short int mu[N];
bool vis[N];
int prime[N],tot=0;
ll phi[N],f[N],g[N];
void pre(){
    phi[1]=mu[1]=1;
    for(int i=2;i<N;i++){
        if(!vis[i])prime[++tot]=i,phi[i]=i-1,mu[i]=-1;
        for(int j=1;j<=tot&&i*prime[j]<N;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j]==0){
                mu[i*prime[j]]=0;
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            mu[i*prime[j]]=-mu[i];
            phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }    
    }
    for(int i=1;i<N;i++){
        phi[i]+=phi[i-1];
        if(phi[i]>=p)phi[i]%=p;
        for(int j=i;j<N;j+=i)f[j]++;
        f[i]+=f[i-1];
        if(f[i]>=p)f[i]%=p;
    }
    for(int i=1;i<N;i++){
        if(mu[i])
        for(int j=i;j<N;j+=i){
            g[j]+=mu[i]*f[j/i];
            if(g[j]>=p)g[j]%=p;
            if(g[j]<0)g[j]=(g[j]%p+p)%p;    
        }
        g[i]+=g[i-1];
        if(g[i]>=p)g[i]%=p;
    }
}
int main(){pre();int n;while(scanf("%d",&n)>0)printf("%lld\n",(g[n]+phi[n]-n)%p);}