luogu2568 gcd

#define mp make_pair
#define pb push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
inline LL ()
{
	LL 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=1e7+8;
int n;
bool not_pri[N];
int pri[N],phi[N/2],num;
LL sum[N/2],ans;
int main()
{
	n=read();
	
	for(int i=2;i<=n;++i){
		if(!not_pri[i]){
			pri[++num]=i;
			if(i<=n/2)	phi[i]=i-1;
		}
		if(i<=n/2)	sum[i]=sum[i-1]+phi[i];
		int j;
		for(j=1;j<=num&&pri[j]<=n/i;++j){
			not_pri[pri[j]*i]=1;
			if(i%pri[j]){
				if(pri[j]<=n/2/i)	phi[pri[j]*i]=phi[i]*(pri[j]-1);
			}
			else{
				if(pri[j]<=n/2/i)	phi[pri[j]*i]=phi[i]*pri[j];
				break;
			}
		}
	}
	for(int i=1;i<=num;++i){
		ans+=sum[n/pri[i]];
	}
	printf("%lld",ans*2+num);
	return 0;
}