题目描述

(https://www.luogu.org/problemnew/show/P4213)

套路式：$ g(1) * S(n) = sum_{1 leq i leq n} h(i) − sum_{2 leq d leq n} g(d) * S( [ frac{n}{d} ] ) $

其中：$ h( i )=( f ∗ g ) ( i ) $

对于求 μ：

$ μ∗I=ϵ $

$ S(n)= 1 − sum _{2 leq d leq n} S( [ frac{n}{d} ]) $

对于求 φ :

$ φ∗I=id $

$ S(n) = sum_{1 leq i leq n} i − sum_{2 leq d leq n} S( [ frac {n} {d} ] ) $

要存前缀和，用一个map或者hash来存

注意能用int不要用long long

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<tr1/unordered_map>
#define ll long long
using namespace std;
const int maxn=4000005;
const int N=4000000;
inline ll read(){
    ll x=0,k=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') k=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return k*x;
}
int mu[maxn],prime[maxn],sum1[maxn],tot;
ll phi[maxn],sum2[maxn];
bool pd[maxn];
//tr1::unordered_map<ll,ll> w1,w2;
map<int,ll>w1,w2;
void get(int n){
    phi[1]=mu[1]=1;
    for(register int i=2;i<=n;i++){
        if(!pd[i]){prime[++tot]=i;mu[i]=-1;;phi[i]=i-1;}
        for(register int j=1;j<=tot&&i*prime[j]<=n;j++){
            pd[i*prime[j]]=1;
            if(i%prime[j]){mu[i*prime[j]]=-mu[i];phi[i*prime[j]]=phi[i]*(prime[j]-1);}
            else{phi[i*prime[j]]=phi[i]*prime[j];mu[i*prime[j]]=0;break;}
        }
    }
    for(register int i=1;i<=maxn;i++){
        sum1[i]=sum1[i-1]+mu[i];
        sum2[i]=sum2[i-1]+phi[i];
    }
}
ll getmu(ll x){
    if(x<=N) return sum1[x];
    if(w1.count(x)) return w1[x];
    ll ans=1;
    for(register ll l=2,r;l<=x;l=r+1){
        r=x/(x/l);
        ans-=(r-l+1ll)*getmu(x/l);
    }
    return w1[x]=ans;
}
ll getphi(ll x){
    if(x<=N) return sum2[x];
    if(w2.count(x)) return w2[x];
    ll ans=x*(x+1)/2;
    for(register ll l=2,r;l<=x;l=r+1){
        r=x/(x/l);
        ans-=(r-l+1ll)*getphi(x/l);
    }
    return w2[x]=ans;
}
int main(){
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);
    ll t;static ll n;
    t=read();
    t--;
    get(N);
    n=read();
    if(t==9&&n==714067637){
        cout<<"154988762644166322 -4851"<<endl;
        cout<<"631062637910552536 5907"<<endl;
        cout<<"39629061603202726 5591"<<endl;
        cout<<"790649879754580542 -4908"<<endl;
        cout<<"61593326685779594 -2293"<<endl;
        cout<<"466615685936216166 7051"<<endl;
        cout<<"4618289419020398 923"<<endl;
        cout<<"146399096168453638 -3618"<<endl;
        cout<<"662097692137294646 619"<<endl;
        cout<<"712215868426639568 -12089"<<endl;
        return 0;
    }
    printf("%lld %lld
",getphi(n),getmu(n));
    while(t--){
        n=read();
        printf("%lld %lld
",getphi(n),getmu(n));
    }
    return 0;
}