首页 > itarticle > bzoj[2818]-gcd

bzoj[2818]-gcd

admin 11月 13, 2020 0

Description

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

简易题解

此题显然需要求 $gcd(x,y)=p_{i} quad x,yin[1,N]$ 。
我们可以将其转化成求 $gcd(x,y)=1 quad x,yin[1,N/p_{i}]$ 。
不妨设 x < y，那么上式就变成了求φ(y)的前缀和，然后×2即可。
由于是有序数对，需要最后需要－1。


#include<cstdio>
#include<cstring>
#include<bitset>
#define LL long long 
using namespace std;
const int N=10000005;
int p_table[N/7];
int p_cnt;
bitset<N> isp;
int phi[N];
LL f[N];
int n;

void (){
	p_cnt=1;
	isp.set();    
	for(int i=2;i<=N;i++){
		if(isp[i]){
			p_table[p_cnt++]=i;
			phi[i]=i-1;
		}
		for(int j=1;i*p_table[j]<=N&&j<p_cnt;j++){
			isp[p_table[j]*i]=0;
			if(!(i%p_table[j])){
				phi[i*p_table[j]]=phi[i]*p_table[j];
				break;
			}else
				phi[i*p_table[j]]=phi[i]*(p_table[j]-1);
		}
	}
	p_cnt--;
	f[1]=1;
	for(int i=2;i<N;i++)
		f[i]=f[i-1]+phi[i];
}
	
LL getAns(){
	LL ans=0;
	for(int i=1;i<=p_cnt&&p_table[i]<=n;i++)
			ans+=2*f[n/p_table[i]]-1;
	return ans;
}

int main(){
	getTable();
	scanf("%d",&n);
	printf("%lldn",getAns());
	return 0;
}