你说的对，这题是欧拉函数题，但是我有更有拓展性的莫比乌斯反演做法。

声明：下文中方括号代指 $Iverson$ 括号，$[x]$ 相当于 (x==True?1:0)

前置：$[i=1] = \sum_{d \mid i} mu(d)$。

开始退狮子：

$$\begin{aligned} \sum_i^n \sum_j^n [\gcd(i,j) \in prime] &= \sum_{p \in prime} \sum_i^n \sum_j^n [\gcd(i,j) = p] \\&= \sum_{p \in prime} \sum_i^{\lfloor \frac{n}{p} \rfloor} \sum_j^{\lfloor \frac{n}{p} \rfloor} [\gcd(i,j) = 1] \\&= \sum_{p \in prime} \sum_i^{\lfloor \frac{n}{p} \rfloor} \sum_j^{\lfloor \frac{n}{p} \rfloor} \sum_{d \mid \gcd(i,j)} \mu(d) \\ &= \sum_{p \in prime} \sum_d \mu(d) \sum_i^{\lfloor \frac{n}{pd} \rfloor} \sum_j^{\lfloor \frac{n}{pd} \rfloor} 1 \\&= \sum_{p \in prime} \sum_d \mu(d) \lfloor \frac{n}{pd} \rfloor^2 \end{aligned}$$

这个看起来没法化简了，但是我们要拿出莫比乌斯反演的经典套路：枚举 $pd$。

令 $pd = T$，则原式等于：

$$\sum_T^n \lfloor \frac{n}{T} \rfloor^2 \sum_{p \in prime,p \mid T} \mu(\frac{T}{p}) $$

令：

$$f(n) = \sum_{p \in prime,p \mid T} \mu(\frac{T}{p}) $$

这个可以预处理，具体见代码。

然后求一个前缀和，再应用数论分块，这题就做完了。

复杂度 $O(M + \frac{M}{\ln M} \times \log M + \sqrt{M}) = O(M + \sqrt{M})$。

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
int T,n,m;
int N;
signed pri[1001000],miu[10001000],isp[10001000],tot;
int f[10001000];
void sieve(){
	miu[1]=1;
	for(int i=2;i<=N;i++){
		if(!isp[i]) pri[++tot]=i,miu[i]=-1;
		for(int j=1;j<=tot&&i*pri[j]<=N;j++){
			isp[i*pri[j]]=1;
			if(i%pri[j]){
				miu[i*pri[j]]=-miu[i];
			}
			else{
				miu[i*pri[j]]=0;
				break;
			}
		}
	}
	for(int i=1;i<=tot;i++){
		for(int j=1;j*pri[i]<=N;j++){
			f[j*pri[i]]+=miu[j];
		}
	}
	for(int i=1;i<=N;i++){
		f[i]+=f[i-1];
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	N=n;
	sieve();
	int i=1,ans=0;
	while(i<=n){
		int j=n/(n/i);
		ans+=(n/i)*(n/i)*(f[j]-f[i-1]),i=j+1;
	}
	cout<<ans<<'\n';
	return 0;
}