Jennie

素数不多，我们考虑素数就可以了

对于素数来说，能以他为gcd，那么肯定时它的倍数，且$gcd(frac{i}{prime},frac{j}{prime})=1$，那么我们先求出$1-n$有多少个prime的倍数，然后取出两个互质的倍数，就是一个答案

这不就时$phi()$的干的好事

最后求个和，处理一下.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
int prime[1000006];
int vis[10000005];
int phi[10000005];
int sum[10000005];
int n;
int p;
void ini(){
    phi[1]=1;
    sum[1]=1;
    for(int i=2;i<=n;++i){
        if(!vis[i]){
            p++;
            prime[p]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=p&&i*prime[j]<=n;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }else{
                phi[i*prime[j]]=phi[i]*phi[prime[j]];
            }
        }
        sum[i]=sum[i-1]+phi[i];
    }
}
int ans;
signed main(){
    scanf("%d",&n);
    ini();
    for(int i=1;i<=p;++i){
            ans+=(2*sum[n/prime[i]]-1);
    }
    cout<<ans;
    return 0;
}