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 筛法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。