最大公约数

发表于2022-06-02更新于2022-06-02

题目描述

220. 最大公约数 - AcWing题库

样例

1
输入:4 输出:4

算法1

算法

gcd(x,y)==素数 P ,且1<=x,y<=N

显然gcd(x/p,y/p)==1,然后这就联想到欧拉函数，1~n里有多少个数互质。

先说结论

1
2
3
4
for(int i=1;i<=cnt;i++)
   {
       ans+=pre[n/primes[i]]<<1|1;//pre数组就是欧拉函数
   }

我解释一下我看题解的时候遇到一些疑惑

1.为什么 ans为什么每次加上的是pre[n/primes[i]]*2+1？

  pre[i]是1~N中互质的对数，但是题目中的x,y是分顺序的，所以要乘以2，为什么加1，因为x,y为相同的一个质数的时候也是符合条件的x，y;

2.ans每次加上pre[n/primes[i]]*2+1不会有数对已经被统计过了还会再被统计吗？

for(int i=1;i<=cnt;i++)循环是把所有的（x,y）进行了一个集合的划分，也就是gcd(x,y)=primes[i1];

所以如果这对x,y在这一i的循环出现过（说明说明gcd(x,y)==p[i1])。当i2!=i1 在i2的集合中那gcd(x,y)==p[i2],且p[i2]!=p[i1],所以不可能一对(x,y)中多次被记录

C++ 代码

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
#include<bits/stdc++.h>

using namespace std;
#define int long long

int primes[11000000];
bool st[11000000];
int pre[11000000];
int cnt=0;
void init(int k){
    for(int i=2;i<=k;i++){
        if(!st[i]){
            primes[++cnt]=i;
            pre[i]=i-1;
        }
        for(int j=1;j<=cnt&&i*primes[j]<=k;j++){
            st[i*primes[j]]=1;
            if(i%primes[j]==0){  pre[i*primes[j]]=pre[i]*primes[j]; break;}
            pre[i*primes[j]]=pre[i]*(primes[j]-1);
        }
      pre[i]=pre[i-1]+pre[i];
    }
}

signed main(){
    int n;
    cin>>n;
    init(n);
    int ans=0;
    for(int i=1;i<=cnt;i++)
    {
        ans+=pre[n/primes[i]]<<1|1;
    }
    cout<<ans<<endl;
    
    
}

所以呢就别不快乐。