感觉码风还算可以

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int Mu[2000001];
int Prime[300000];
int vis[2000001];
void CalMu(int n)
{
	Mu[1]=1;
	int tot=0;
	for(int i=2;i<=n;i++)
	{
		if(!vis[i])
		{
			Prime[++tot]=1;
			Mu[i]=-1;
		}
		for(int j=1;j<=tot && i*Prime[j]<=n;j++)
		{
			vis[i*Prime[j]]=1;
			if(i%Prime[j]==0)	break;
			Mu[i*Prime[j]]=-Mu[i];
		}
	}
	for(int i=2;i<=n;i++)	Mu[i]+=Mu[i-1];
}
inline ll solve(ll m)
{
	ll ans=0;
	for(int l=1,r;l<=m;l=r+1)
	{
		r=m/(m/l);
		ans+=(Mu[r]-Mu[l-1])*(m/l)*(m/l);
	}
	return ans;
}
int main()
{
	ll n;
	cin>>n;
	CalMu(n);
	ll ans=0;
	for(int l=1,r;l<=n;l=r+1)
	{
		r=n/(n/l);
		ans+=((l+r)*(r-l+1)/2)*solve(n/l);
	}
	cout<<(ans-(n+1)*n/2)/2<<endl;	
}

思路：

$\sum\limits_{i,j∈[1,n]}\gcd(i,j)=\sum\limits_{g=1}^ng\sum\limits_{d=1}^m\mu(d)[\dfrac{m}{d}]^2\ \ \mathrm{where\ }\ m=[\dfrac{n}{g}]$