[数论]bzoj2818 gcd

bzoj2818
一道欧拉函数的题目qwq

题意

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

输入和输出

Input
一个整数N
1<=N<=10^7

Output
如题

Sample Input
4

Sample Output
4
HINT

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

题解

求gcd(x,y)为素数的x和y对数,可将问题转换为,找互质的x,y和一个质数,满足x,y分别乘同一个素数后小于n。
假设x<y,则对于每个y<n,求phi(y),即与y互质的数的个数,再求有多少质数乘y后小于n。
具体做法:

  • 线性复杂度求小于n的数的欧拉函数euler[i]
  • 线性筛小于n的素数(vis[i]为0则为质数)
  • 求!vis的前缀和sum[i],即为小于i的数有多少个数是质数。
  • 求 $\sum _ {i=2}^{n-1}euler[i]* sum[n/i]$ 即为答案

快乐代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
using namespace std;
typedef long long ll;
const ll MAXN=40005;
ll euler[MAXN];
ll sum[MAXN];
ll vis[MAXN];
ll prime[MAXN];

void Init(){
euler[1]=1;
for(ll i=2;i<MAXN;i++)
euler[i]=i;
for(ll i=2;i<MAXN;i++)
if(euler[i]==i)
for(ll j=i;j<MAXN;j+=i)
euler[j]=euler[j]/i*(i-1);
}

int f(int n)
{
int cnt =0;
for(int i=2;i<=n;i++){
if(!vis[i]) prime[cnt++] = i;
for(int j=0;j<cnt && i*prime[j]<=n;j++){
vis[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
return cnt;
}

int main(){
Init();
int n;cin>>n;
int cnt=f(n);
sum[0]=0;sum[1]=0;
for(int i=2;i<=n;i++) sum[i]=sum[i-1]+(!vis[i]);
int ans=0;
for(int i=2;i<n;i++){
ans+=euler[i]*sum[n/i];
}
cout<<ans*2+cnt<<endl;
return 0;
}