「BZOJ2818」Gcd

2014年6月15日8,1750

Description

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

Input

一个整数N

Output

如题

Sample Input

Sample Output

HINT

hint
对于样例(2,2),(2,4),(3,3),(4,2)

1<=N<=10^7

题解

wulala：~~很水的一道数论题~~

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

枚举每个素数，然后每个素数p对于答案的贡献就是（1 ~ n / p）中有序互质对的个数
而求1~m中有序互质对x，y的个数，可以令y >= x, 当y = x时，有且只有y = x = 1互质，当y > x时，确定y以后符合条件的个数x就是phiy
所以有序互质对的个数为（1 ~ n/p）的欧拉函数之和乘2减1（要求的是有序互质对，乘2以后减去（1， 1）多算的一次）
那么就只需要先筛出欧拉函数再求个前缀和就可以了

#include<iostream>
#include<cstdio>
#define ll long long
#define N 10000005
using namespace std;
int n,p,tot;
int phi[N],pri[1000005];
bool mark[N];
ll ans,sum[N];
void getphi()
{
	phi[1]=1;
	for(int i=2;i<=n;i++)
	{
		if(!mark[i]){phi[i]=i-1;pri[++tot]=i;}
		for(int j=1;j<=tot;j++)
		{
			int x=pri[j];
			if(i*x>n)break;
			mark[i*x]=1;
			if(i%x==0){phi[i*x]=phi[i]*x;break;}
			else phi[i*x]=phi[i]*phi[x];
		}
	}
}
int main()
{
	scanf("%d",&n);
	getphi();
	for(int i=1;i<=n;i++)
	    sum[i]=sum[i-1]+phi[i];
	for(int i=1;i<=tot;i++)
	    ans+=sum[n/pri[i]]*2-1;
	printf("%lld",ans);
	return 0;
}

#include<iostream>

#include<cstdio>

#define ll long long

#define N 10000005

using namespace std;

int n,p,tot;

int phi[N],pri[1000005];

bool mark[N];

ll ans,sum[N];

void getphi()

{

phi[1]=1;

for(int i=2;i<=n;i++)

{

if(!mark[i]){phi[i]=i-1;pri[++tot]=i;}

for(int j=1;j<=tot;j++)

{

int x=pri[j];

if(i*x>n)break;

mark[i*x]=1;

if(i%x==0){phi[i*x]=phi[i]*x;break;}

else phi[i*x]=phi[i]*phi[x];

}

int main()

{

scanf("%d",&n);

getphi();

for(int i=1;i<=n;i++)

sum[i]=sum[i-1]+phi[i];

for(int i=1;i<=tot;i++)

ans+=sum[n/pri[i]]*2-1;

printf("%lld",ans);

return 0;

}

« 「POJ2407」Relatives 「BZOJ2705」[SDOI2012] Longge的问题 »

hzwer.com _ Home | http://hzwer.com

「BZOJ2818」Gcd

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论