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); }

转载于:https://www.cnblogs.com/qscqesze/p/5403692.html

总结

以上是生活随笔为你收集整理的BZOJ 2818: Gcd 筛法的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。