LGOJ2568 GCD

Description

link

给定整数(n)，(1 leq x,y leq n)且(gcd(x,y))为质数的((x,y))的对数

[1leq nleq 10^7 ]

Solution

(O(n^2space log space n))的枚举肯定会爆，所以我们换一个统计方法

从质数入手，所以题意转化为求

[sum _ {p in prime} sum _ {i=1} ^{n} sum_{j=1}^n [gcd(i,j)==p] ]

处理(gcd) ，进行套路性变形

[sum _ {p in prime} sum _ {i=1} ^{lfloor frac{n}{p} floor} sum _ {j=1} ^{lfloor frac{n}{p} floor} [gcd(i,j)==1] ]

下面我们改变(j)的枚举上界（就是因为有对称性嘛）

[sum _ {p in prime} sum _ {i=1} ^{lfloor frac{n}{p} floor}(2 imes sum _ {j=1} ^{i} [gcd(i,j)==1]-1) ]

这里的减(1)是因为(i=j=1)的时候答案会被重复统计

这个地方显然是有一些我们很熟悉的东西：(varphi)

线性筛欧拉函数和质数就完事了

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace yspm{
	inline int read()
	{
		int res=0,f=1; char k;
		while(!isdigit(k=getchar())) if(k=='-') f=-1;
		while(isdigit(k)) res=res*10+k-'0',k=getchar();
		return res*f;
	}
	const int N=1e7+10,M=1e6+10;
	int n,tot,p[M],phi[N],sum[N];
	bool fl[N];
	inline void prework()
	{
		phi[1]=1;
		for(int i=2;i<=n;++i)
		{
			if(!fl[i]) p[++tot]=i,phi[i]=i-1;
			for(int j=1;j<=tot&&i*p[j]<=n;++j)
			{
				fl[i*p[j]]=1; 
				if(i%p[j]==0){phi[i*p[j]]=phi[i]*p[j]; break;}
				else phi[i*p[j]]=phi[i]*phi[p[j]];
			}
		} for(int i=1;i<=n;++i) sum[i]=sum[i-1]+phi[i];
		return ;
	}
	signed main()
	{
		n=read(); prework(); int ans=0;
		for(int i=1;i<=tot;++i) ans+=2*sum[n/p[i]]-1;
		printf("%lld
",ans);
		return 0;
	}
}
signed main(){return yspm::main();}