BZOJ 2818: Gcd 欧拉函数

本文主要是介绍BZOJ 2818: Gcd 欧拉函数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

继续复制QSC  https://www.cnblogs.com/qscqesze/p/5403692.html

BZOJ 2818: Gcd 筛法

 

2818: Gcd

题目连接：

http://www.lydsy.com/JudgeOnline/problem.php?id=2818

Description

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

Input

一个整数N

Output

如题

Sample Input

4

Sample Output

4

Hint

题意

题解：

gcd(x,y) = p的对数

等于 gcd(x/p,y/p)=1的对数

那么实际上就是求sigma(phi)，但是这个玩意儿是有序的

那么我们就乘以2，再减去一个(1,1)这个东西就好了。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e7+5;long long phi[maxn];
int prime[maxn],num;
int n;
void phi1()
{phi[1]=1;for(long long i=2;i<=n;i++){if(!phi[i]){prime[num++]=i;for(long long j=i;j<=n;j+=i){if(!phi[j]) phi[j]=j;phi[j]=phi[j]/i*(i-1);}}}
}
int main()
{scanf("%d",&n);phi1();long long ans = 0;for(int i=1;i<=n;i++)phi[i]+=phi[i-1];for(int i=0;i<num;i++)ans+=phi[n/prime[i]];printf("%lld\n",2*ans-num);
}

这个题目是是从gcd(x, y) = 1演变来的。注意qsc这个phi之后变成了前缀和!(只要x*prime[i]<=n, 那么因为phi[x]计算的是比x小的和x互质的数，所以y*prime[i]<=n)

这篇关于BZOJ 2818: Gcd 欧拉函数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---