[luogu 2568] GCD （欧拉函数）

题目描述

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

输入输出格式

输入格式：

一个整数N

输出格式：

答案

输入样例#1：

输出样例#1：

说明

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

1<=N<=10^7

上午用这道题考试（虽然略有区别不过差不多）qwq

用欧拉函数乱推。。。

code:(ac代码)

#include<cstdio>

#define LL long long

const int N=10000010;

int n,cnt;

int pri[N],phi[N];

LL ans;

LL qphi[N];

bool vis[N];

void init() {

	vis[1]=phi[1]=1;

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

		if(!vis[i]) pri[++cnt]=i,phi[i]=i-1;

		for(int j=1;j<=cnt && pri[j]*i<=n;j++) {

			vis[pri[j]*i]=1;

			if(!(i%pri[j])) {phi[i*pri[j]]=phi[i]*pri[j];break;}

			else phi[i*pri[j]]=phi[i]*phi[pri[j]];

		}

	}

	for(int i=1;i<=n;i++) qphi[i]=qphi[i-1]+phi[i];//前缀和

}

int main() {

	scanf("%d",&n);

	init();

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

		ans+=(qphi[(n-n%pri[i])/pri[i]]<<1)-1;

                    //稍微解释：因为每次枚举中有一种情况为(pi,pi) (pi为范围内第i个素数) 应被算作一种其余的都应乘2

                    //也可以刚开始按乘2算出来最后减去素数个数

	printf("%lld",ans);

	return 0;

}

code:(考试原代码)

PS：由于考题与本题略有不同不能过本题而且懒得改了，此处仅为记录原考题（即(2,4)与(4,2)视作一种情况）的代码

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<ctime>

#define LL long long

using namespace std;

const int N=10000010;

int n,cnt;

LL ans;

int pri[N/10],phi[N];

LL qphi[N];

bool vis[N];	

int gcd(int a,int b) {//原始暴力算法(n^2)

	return !b?a:gcd(b,a%b);

}

void init() {//欧拉筛

	vis[1]=1;phi[1]=1;

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

		if(!vis[i]) pri[++cnt]=i,phi[i]=i-1;

		for(register int j=1;j<=cnt && pri[j]*i<=n;j++) {

			vis[pri[j]*i]=1;

			if(i%pri[j]==0) {

				phi[i*pri[j]]=phi[i]*pri[j];

				break;

			}

			else phi[i*pri[j]]=phi[i]*phi[pri[j]];

		}

	}

	for(int i=1;i<=n;i++) qphi[i]=qphi[i-1]+phi[i];

}

int get(int x) {//高级暴力的二分

	if((x<<1)>n) return 0;

	int l=1,r=cnt;

	while(l<r) {

		int mid=(l+r+1)>>1;

		if(pri[mid]*x<=n) l=mid;

		else r=mid-1;

	}

	return l;

}

int main() {

	// freopen("gcd.in","r",stdin);

	// freopen("gcd.out","w",stdout);

	scanf("%d",&n);

//	int be=clock();

	init();

//	for(register int i=1;i<=n;i++) {//比较快的暴力算法（nlogn）。。

//		int x=get(i);

//		ans+=x*phi[i];

//	}

//	printf("%lld",ans);

//	ans=0;cout<<endl;

	for(register int i=1;i<=cnt;i++) {//能过的~~暴力~~算法(n)

		int x=(n-n%pri[i]);

		ans+=qphi[x/pri[i]];

	}

	// cout<<cnt<<endl;

	printf("%lld",ans);

//	int ed=clock();

//	cout<<endl<<ed-be;

	return 0;

}

巴特西

[luogu 2568] GCD （欧拉函数）

题目描述

输入输出格式

说明

最新文章

热门文章