统计互质的对数——欧拉函数

参考博客 https://www.luogu.com.cn/blog/zykblog/p2568

1 < x,y < n 且（x,y）=p

$\Rightarrow$ 1< k1*p,k2*p < n 【不妨设k1<k2】 (k1,k2)=1

==> 看到互质（统计互质的对数）——欧拉函数

所以p不同时，互质的对数也不同

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const N=1e7+7;
int n,cnt;
int phi[N],p[N];
ll a[N];
bool v[N];
int main(){
	phi[1]=1;a[1]=1;
	cin >> n;
	for(register int i=2;i<=n;++i){
		if(v[i]==0){
			p[++cnt]=i;
			phi[i]=i-1;
		}
		for(register int j=1;j<=cnt&&p[j]*i<=n;++j){
			v[ p[j]*i ]=1;
			if(i%p[j]==0){
				phi[ p[j]*i ]=phi[i]*p[j];
				break;
			}
			else phi[ p[j]*i ]=phi[i]*(p[j]-1);
		}	
		a[i]=a[i-1]+phi[i];   //对phi做前缀和，表示左边相对固定，x以内的互质对数
	}
	ll ans=0;
	for(int i=1;i<=cnt&&p[i]<=n;++i){
		ans+=(a[n/p[i]])*2-1;    //*2表示左右可以互换，-1表示(p,p)=p这种只能算一种
	}
	cout << ans;
	return 0;
}