先预处理欧拉函数，再用整除分块枚举 gcd 再用欧拉函数计算答案，时间 $O(n\sqrt{n}\log n)$，居然 A 了？

#include<bits/stdc++.h>
using namespace std;
int n,x,a[150000],c[2000005];
bool b[2000005];
long long ans=0;
int gcd(int x,int y)
{
	return x%y==0?y:gcd(y,x%y);
}
int main()
{
	cin>>n;
	for (int i=2;i<=n;++i)
	{
		if (!b[i])
		{
			a[++a[0]]=i;
			c[i]=i-1;
		}
		for (int j=1;j<=a[0] && i*a[j]<=n;++j)
		{
			b[i*a[j]]=1;
			if (i%a[j])
			c[i*a[j]]=c[i]*c[a[j]];
			else
			{
				c[i*a[j]]=c[i]*a[j];
				break;
			}
		}
	}
	for (int k=1;k<=n;k=x+1)
	{
		x=n/(n/k);
		for (int i=2;i<=n/k;++i)
		ans+=((long long)(k+x)*(x-k+1)>>1)*c[i];
	}
	cout<<ans;
}