我的算法书 - GCD

题目描述

给定正整数 $n$ ，求 $1\le x,y\le n$ 且 $\gcd(x,y)$ 为素数的数对 $(x,y)$ 有多少对。

数据范围： $1\le n\le 10^7$ 。

解题思路

1 问题转化

直接枚举x,y 是 $n^2$ 的,这里使用构造法,固定一个p,然后求出p对应的(x,y)的数量: 这里显然是O(1)的

题目要求统计满足 $\gcd(x, y) = p$ （ $p$ 为素数）的数对数量。我们可以按照素数 $p$ 来分类统计。

对于一个固定的素数 $p$ ，如果 $\gcd(x, y) = p$ ，那么 $x$ 和 $y$ 一定都是 $p$ 的倍数。我们可以设：

x = a \times p

y = b \times p

此时， $x, y \in [1, n]$ 等价于 $a, b \in [1, \lfloor \frac{n}{p} \rfloor]$ 。同时，为了保证 $\gcd(x, y)$ 恰好为 $p$ 而不是 $p$ 的倍数，必须满足：

\gcd(a, b) = 1

结论：对于每一个素数 $p$ ，问题的贡献转化为：在 $1$ 到 $\lfloor \frac{n}{p} \rfloor$ 的范围内，有多少对 $(a, b)$ 互质。

其实这里的思想就是: 按公约数p,对x,y近性分类,通过函数的逆运算, 求出p对应的集合 $A = \{(a_i,b_i)\}$ ,只要找到这个集合,就知道对以的素数p的数量.同样我们也可以知道其他的 $p_2$ 对应的数量. 然后对应的数量加起来,就是答案.

问题就变成有多少对 $(a,b)$ ,符合条件

$gcd(a,b) = 1$
$a,b \in [1, \lfloor \frac{n}{p} \rfloor]$

最简单的就是二重循环枚举. 问题变成怎么快速枚举.

这里编程枚举对数(黑白气球),这里假定 $b > a$ , 那么固定b,的时候,问题就变成了 $[1,b)$ 里面有多少元素和b互质. 这不就是欧拉函数吗?

2 利用欧拉函数求解互质对

令 $k = \lfloor \frac{n}{p} \rfloor$ 。我们需要求 $1 \le a, b \le k$ 中 $\gcd(a, b) = 1$ 的对数。

利用图形的对称性，我们可以将 $k \times k$ 的矩阵分为三部分：

下三角 ( $a > b$ )：满足 $\gcd(a, b) = 1$ 的数量。根据欧拉函数的定义，对于固定的 $a$ ，满足 $b < a$ 且 $\gcd(a, b)=1$ 的 $b$ 的个数就是 $\phi(a)$ 。
上三角 ( $b > a$ )：由对称性可知，数量与下三角相同。
对角线 ( $a = b$ )：只有 $(1, 1)$ 这一对满足 $\gcd(1, 1) = 1$ 。

因此，对于上限 $k$ ，互质对的总数为：

Count(k) = 2 \times \sum_{i=1}^{k} \phi(i) - 1

(减 1 是因为 $(1,1)$ 在求和中被计算了两次，或者理解为：下三角+上三角+对角线)

这里显然是求: $\phi(i)$ 的前缀和

3 最终公式

我们需要对 $1$ 到 $n$ 之间的所有素数 $p$ 进行累加。设 $sum[k] = \sum_{i=1}^k \phi(i)$ 为欧拉函数的前缀和。

最终答案为：

Ans = \sum_{p \in Primes, p \le n} (2 \times sum[\lfloor \frac{n}{p} \rfloor] - 1)

算法实现：线性筛 (Linear Sieve)

由于 $n$ 高达 $10^7$ ，我们需要一种 $O(n)$ 的方法预处理出：

所有质数。
欧拉函数 $\phi(i)$ 。

这可以使用**线性筛（欧拉筛）**来实现。

线性筛推导 $\phi$ 函数

欧拉函数 $\phi$ 是积性函数，在线性筛过程中可以顺便计算：

基础情况： $\phi(1) = 1$ 。
当 $i$ 是素数时： $\phi(i) = i - 1$ 。
当 $i$ 与素数 $p$ 互质时 ( $i \% p \neq 0$ )：利用积性性质： $\phi(i \times p) = \phi(i) \times \phi(p) = \phi(i) \times (p - 1)$ 。
当 $i$ 被素数 $p$ 整除时 ( $i \% p == 0$ )：此时 $p$ 已经是 $i$ 的因子，增加一个 $p$ 不会增加新的质因子种类： $\phi(i \times p) = \phi(i) \times p$ 。

复杂度分析

时间复杂度：线性筛预处理为 $O(n)$ ，统计答案遍历所有素数，复杂度约为 $O(\frac{n}{\ln n})$ ，总体为 $O(n)$ 。
空间复杂度：需要数组存储素数表、标记数组和 $\phi$ 数组，约为 $O(n)$ 。

代码实现 (C++)

我的代码

cpp

copy

        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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

        #include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll n;
const ll maxn = 1e7+5;

ll phi[maxn]; // 欧拉函数
bool st[maxn]; // st[i] = 1 表示被删除,不是素数
std::vector<ll> primes; //存素数
ll sum[maxn]; // 欧拉函数的前缀和
ll ans; // 最终答案

void get_phi_line(){
    phi[1] = 1;
    for(int i = 2;i <= n ;++i ) // i: 2->n
    {

        if( !st[i])
        {
            primes.push_back(i);
            phi[i] = i - 1;
        }

        //枚举前面的素数
        for(auto p : primes) {

            if( i * p > n) break;
            st[i * p ] = 1;

            if( i % p == 0) {
                phi[i * p] = phi[i] * p;
                break;
            }
            else {
                phi[p * i] = phi[i] * (p-1); 
            }

        }
    }
}



int main (int argc, char *argv[]) {
    scanf("%lld",&n);

    get_phi_line();

    // 求phi前缀和

    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        sum[i] = sum[i-1] + phi[i];
    }

    // 枚举素数
    for( auto p : primes) {
        ans += ( 2 * sum[n/p] - 1);
    }
    std::cout << ans << "\n";
    
    return 0;
}

cpp