Problem 2818. -- Gcd

题意

F.A.Qs	Home	Discuss	ProblemSet	Status	Ranklist	Contest	入门OJ	ModifyUser autoint	Logout	捐赠本站

Problem 2818. -- Gcd

2818: Gcd

Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 9590 Solved: 4263
[Submit][Status][Discuss]

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

Source

湖北省队互测

[Submit][Status][Discuss]
HOME Back

分析

参照hzwer的题解。

枚举每个素数，然后每个素数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）多算的一次）
那么就只需要先筛出欧拉函数再求个前缀和就可以了

时间复杂度(O(n))

代码

#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
    rg T data=0,w=1;rg char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}
    while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();
    return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;

co int N=1e7+1;
int n,p[N];
ll phi[N],ans;
int main(){
//	freopen(".in","r",stdin),freopen(".out","w",stdout);
	read(n);
	phi[1]=1;
	for(int i=2;i<=n;++i){
		if(!p[i]) p[++p[0]]=i,phi[i]=i-1;
		for(int j=1;j<=p[0]&&i*p[j]<=n;++j){
			p[i*p[j]]=1;
			if(i%p[j]==0) {phi[i*p[j]]=phi[i]*p[j];break;}
			phi[i*p[j]]=phi[i]*phi[p[j]];
		}
	}
	for(int i=2;i<=n;++i) phi[i]+=phi[i-1];
	for(int i=1;i<=p[0];++i) ans+=phi[n/p[i]]*2-1;
	printf("%lld
",ans);
	return 0;
}