题目描述

给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的数对(x,y)有多少对.

输入格式 Input Format

一个整数$N。N<=10^7$

输出格式 Output Format

输出一个整数，表示满足条件的数对数量.

输入：

4

输出：

4

---

想法

其实，根本用不到gcd，
由于gcd(x,y)为素数,设这个素数为p,所以 $ gcd( \frac{x}{p},\frac{y}{p})=1 $;也就是说每一个小于n的质数p，对于每两个互质的数，都会有一组解（x<=n&&y<=n）
先求出1~n的欧拉函数，之后再求出其前缀和 $ \phi [i] $ 为前n个数的欧拉函数和，表示在1~n中有多少互质数.
再把每一次的乘二再相加，就是要求的sum了

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<utility>
using namespace std;
long long cnt=0,prime[10000010];  
long long phi[10000010];
long long n;
void get()  
{ 
	phi[1]=1;
    for(int i=2;i<=n;i++)  
    { 
        if(!phi[i])
		{
			prime[++cnt]=i;  
			for(int j=i;j<=n;j+=i)  
			{
				if(phi[j]==0)
					phi[j]=j;
				phi[j]=phi[j]/i*(i-1);
			}
        }  
    }  
}
long long sum=0;
int main()
{
	cin>>n;
	//int k=clock();
	//for(int i=1;i<=n;i++)
	//	phi[i]=i;
	get();
	//get2();
	for(int i=1;i<=n;i++) phi[i]+=phi[i-1];
	for(int i=1;i<=cnt;i++)
		sum+=phi[n/prime[i]]*2-1;
	//cout<<clock()-k<<endl;
	cout<<sum<<endl;
	return 0;
}