[题目链接]

给定一个正整数\(N(N\le2^{31}-1)\)

求

\(ans_1=\sum_{i=1}^n\varphi(i)\)

\(ans_2=\sum_{i=1}^n \mu(i)\)

[题解]

// luogu-judger-enable-o2#include
    
     #include
     
      //#define int long longusing namespace std;typedef long long LL;const int INF=1e9+7;inline LL read(){    register LL x=0,f=1;register char c=getchar();    while(c<48||c>57){if(c=='-')f=-1;c=getchar();}    while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar();    return f*x;}const int MAXN=5e6+5;LL mu[MAXN];LL phi[MAXN];int prime[MAXN];bool vis[MAXN];unordered_map 
      
        Smu,Sphi;int n,T;inline void init(int n){    mu[1]=1,phi[1]=1;    for(int i=2;i<=n;i++){        if(!vis[i]){            prime[++prime[0]]=i;            mu[i]=-1;            phi[i]=i-1;        }        int x;        for(int j=1;j<=prime[0]&&(x=(i*prime[j]))<=n;j++){            vis[x]=1;            if(i%prime[j]==0){                mu[x]=0;                phi[x]=1ll*phi[i]*prime[j];                break;            }            mu[x]=-mu[i];            phi[x]=1ll*phi[i]*phi[prime[j]];        }    }    for(int i=2;i<=n;i++)        mu[i]+=mu[i-1],phi[i]+=phi[i-1];}inline LL S_mu(int x){    if(x