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

#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

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 10000010;

// primes: 存储筛出来的素数
// cnt: 记录素数的个数
// vis: 标记数组，false 表示是素数，true 表示是合数
// phi: 存储欧拉函数值
// sum: 存储欧拉函数的前缀和
int primes[MAXN];
int cnt = 0;
bool vis[MAXN];
int phi[MAXN];
long long sum[MAXN]; // 前缀和可能会溢出 int，使用 long long

void get_phi_and_primes(int n) {
    phi[1] = 1;
    
    for (int i = 2; i <= n; ++i) {
        if (!vis[i]) {
            primes[++cnt] = i; 
            phi[i] = i - 1;    // 素数的欧拉函数性质
        }
        
        for (int j = 1; j <= cnt && i * primes[j] <= n; ++j) {
            int p = primes[j];
            int num = i * p;
            
            vis[num] = true;
            
            if (i % p == 0) {
                // p 已经是 i 的最小质因子，这是线性筛的核心
                phi[num] = phi[i] * p;
                break; // 保证每个合数只被筛一次
            } else {
                // p 与 i 互质
                phi[num] = phi[i] * (p - 1);
            }
        }
    }
    
    // 预处理前缀和
    for (int i = 1; i <= n; ++i) {
        sum[i] = sum[i - 1] + phi[i];
    }
}

int main() {
    // 优化 IO
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    if (!(cin >> n)) return 0;
    
    get_phi_and_primes(n);
    
    long long ans = 0;
    
    // 枚举每一个素数 p
    for (int j = 1; j <= cnt; ++j) {
        int p = primes[j];
        if (p > n) break;
        
        // 代入推导公式：2 * sum[n/p] - 1
        ans += (2 * sum[n / p] - 1);
    }
    
    cout << ans << endl;
    
    return 0;
}

目录