HDU-5942 Just a Math(莫比乌斯)

HDU-5942 Just a Math Problem

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int N=1e6+5;
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
#define sc scanf
#define itn int
#define STR clock_t startTime = clock();
#define END clock_t endTime = clock();cout << double(endTime - startTime) / CLOCKS_PER_SEC *1000<< "ms" << endl;

typedef long long ll;
int prime[N],tot=0;
short int mu[N];
bool vis[N];
ll f[N],h[N];
map<ll,int>p;
void pre(){
    f[1]=mu[1]=1;
    for(int i=2;i<N;i++){
        f[i]=1;
        if(!vis[i])prime[++tot]=i,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;
                break;
            }else mu[i*prime[j]]=-mu[i];
        }
    }
    for(int i=1;i<=tot;i++){
        for(int j=prime[i];j<N;j+=prime[i]){
            int n=j,cnt=0;
            while(n%prime[i]==0)n/=prime[i],cnt++;
            f[j]*=1+cnt;
        }
    }
    for(int i=1;i<N;i++)f[i]=(f[i]+f[i-1])%mod,h[i]=h[i-1]+mu[i];
}
ll cal(ll n){
    if(n<N)return f[n];
    if(p[n])return p[n];
    ll ans=0;
    for(ll i=1,last;i<=n;i=last+1){
        last=n/(n/i);
        ans+=n/i*(last-i+1)%mod;
        if(ans>=mod)ans-=ans/mod*mod;
    }
    return p[n]=ans;
}
int main(){
    pre();
    int t,cas=1;
    for(scanf("%d",&t);cas<=t;cas++){
        ll n;scanf("%lld",&n);
        ll ans=0;
        ll q=sqrt(n+0.5);
        for(ll i=1,last;i<=q;i=last+1){
            last=(n/(n/i/i));
            last=sqrt(last+0.3);
            if(h[last]-h[i-1]==0)continue;
            ans+=(h[last]-h[i-1])*cal(n/i/i);
            if(ans>=mod)ans-=ans/mod*mod;
            if(ans<0)ans=(ans%mod+mod)%mod;
        }
        printf("Case #%d: %lld\n",cas,ans);
    }
}