设 $f[x]=\sum_i^N\sum_j^N[gcd(i,j)==x]$

那么答案就是 $Ans=\sum_{prime}f(prime)$

显然 $f$ 可以反演，设 $F[x]=\sum_i^N\sum_j^N[x|gcd(i,j)]$

那么 $F[x]=\sum_{x|d}f[d]$，并且容易得到 $F[x]=\left \lfloor \frac{N}{x} \right \rfloor \left \lfloor \frac{N}{x} \right \rfloor$

直接反演得到 $f[x]=\sum_{x|d}\mu(d/x)F[d]=\sum_{x|d}\mu(d/x)\left \lfloor \frac{N}{x} \right \rfloor \left \lfloor \frac{N}{x} \right \rfloor$

枚举 $x$ 的倍数 $k$，得到 $f[x]=\sum_k\mu(k)\left \lfloor \frac{N}{kx} \right \rfloor \left \lfloor \frac{N}{kx} \right \rfloor$

因为 $\left \lfloor \frac{N}{kx} \right \rfloor=\left \lfloor \frac{\left \lfloor \frac{N}{x} \right \rfloor}{k} \right \rfloor$

所以 $f[x]==\sum_k\mu(k)\left \lfloor \frac{\left \lfloor \frac{N}{x} \right \rfloor}{k} \right \rfloor\left \lfloor \frac{\left \lfloor \frac{N}{x} \right \rfloor}{k} \right \rfloor$

可以数论分块，然后枚举质数 $p$ 并把所有的 $f[p]$ 加起来就是答案了

质数约有 $sqrt(n)$ 个，单次求 $f$ 复杂度 $sqrt(n)$，总复杂度 $O(n)$

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;typedef long long ll;inline int read(){    int x=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }    while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }    return x*f;}const int N=2e7+7;int n,pri[N],mu[N],tot;bool not_pri[N];ll ans;void pre(){    mu[1]=1;    for(int i=2;i<=n;i++)    {        if(!not_pri[i]) pri[++tot]=i,mu[i]=-1;        for(int j=1;j<=tot;j++)        {            ll g=1ll*i*pri[j]; if(g>n) break;            not_pri[g]=1; if(!(i%pri[j])) break;            mu[g]=-mu[i];        }    }    for(int i=2;i<=n;i++) mu[i]+=mu[i-1];}int main(){    n=read(); pre();    for(int i=1;i<=tot;i++)    {        int p=pri[i],m=n/p;        for(int l=1,r;l<=m;l=r+1)        {            r=m/(m/l);            ans+=1ll*(mu[r]-mu[l-1])*(m/l)*(m/l);        }    }    printf("%lld\n",ans);    return 0;}