Moe's CF Life

Appearance

K. Lonely Numbers - 题解 ​

比赛与标签 ​

比赛: Bubble Cup 13 - Finals [Online Mirror, unrated, Div. 1] 标签: binary search, math, number theory, two pointers 难度: *1600

题目喵述~ ​

这道题呀，定义了一种奇妙的 "朋友" 关系。在数字的世界里，如果两个不同的数 a 和 b 满足一个条件，它们就是朋友啦。这个条件是：gcd(a, b)（它俩的最大公约数）、a/gcd(a, b) 和 b/gcd(a, b) 这三个数可以组成一个三角形。

一个数如果在 1 到 n 这个群体里一个朋友都找不到，那它就是个 "孤独" 的数字。我们的任务就是，对于给定的 n，找出在 1, 2, ..., n 这个群体里，到底有多少个这样的孤独数字呢？

输入输出格式喵~

  • 输入: 先是一个整数 t，表示有 t 组测试。接下来有 t 个数，每个数是 n。
  • 输出: 对每个 n，输出 1 到 n 中孤独数字的数量。

举个栗子🌰：当 n=5 时，孤独的数字是 1, 3, 5，所以答案是 3。

猫娘的思路分析喵~ ​

嘿嘿，这个问题看起来有点绕，但只要我们像小猫咪一样，一步步拆解，就能发现其中的奥秘啦！

第一步：翻译 "朋友" 条件 ​

首先，三个数 x, y, z 能组成三角形，需要满足三角形两边之和大于第三边，也就是：

  1. x + y > z
  2. y + z > x
  3. z + x > y

现在，我们把题目里的三个数代进去。令 g = gcd(a, b)，a' = a/g，b' = b/g。根据最大公约数的性质，我们知道 a' 和 b' 是互质的（gcd(a', b') = 1）。 那么，a 和 b 是朋友的条件就是 g, a', b' 能组成三角形。

我们来分析一下这三个不等式：

  1. g + a' > b'
  2. g + b' > a'
  3. a' + b' > g

因为 a 和 b 是不同的数，所以 a' != b'。不妨假设 a' < b'。因为它们是互质的整数，所以 b' - a' >= 1。

  • g + b' > a' 这个不等式总是成立的，因为 g >= 1 并且 b' > a'。
  • a' + b' > g 这个不等式也常常成立。a' 和 b' 是 a 和 b 除以 g 后的部分，通常情况下，它们的和会比 g 大得多。

所以，最关键的约束是 g + a' > b'，也就是 g > b' - a'。因为 a', b' 都是整数，这等价于 g > |a' - b'|。

一句话总结：a 和 b 是朋友，当且仅当 gcd(a, b) > |a/gcd(a, b) - b/gcd(a, b)|。

第二步：哪些数字会是孤独的？ ​

一个数 x 是孤独的，意味着对于集合 {1, 2, ..., n} 中任何一个不等于 x 的 y，它们都不是朋友。

我们来分情况讨论一下数字 x 的性质吧！

情况一：x = 11 会是孤独的吗？我们来给它找个朋友 y > 1 试试。

  • g = gcd(1, y) = 1
  • x' = 1/g = 1
  • y' = y/g = y
  • 朋友条件是 g > |x' - y'|，也就是 1 > |1 - y|。
  • 因为 y >= 2，所以 |1 - y| = y - 1 >= 1。
  • 1 > y - 1 这个不等式永远不会成立！ 所以，1 在任何群体里都交不到朋友，它永远是孤独的。我们的计数器先加一！

情况二：x 是一个素数 p 我们来给素数 p 找朋友 y。

  • 如果 y 是 p 的倍数，比如 y = k*p (k > 1 且 y <= n)。
    • g = gcd(p, kp) = p
    • x' = p/g = 1
    • y' = kp/g = k
    • 朋友条件是 p > |1 - k| = k - 1。
    • 我们还需要满足三角形的另一个条件 x' + y' > g，也就是 1 + k > p。
    • 结合起来，我们需要 p-1 < k < p+1。满足这个条件的整数 k 只有 k=p！
    • 这意味着，如果 y = p*p = p^2 存在于集合 {1, ..., n} 中，那么 p 和 p^2 就是朋友！
    • 所以，如果一个素数 p 满足 p^2 <= n，它就不是孤独的。
  • 如果 y 和 p 互质
    • g = gcd(p, y) = 1
    • x' = p/g = p
    • y' = y/g = y
    • 朋友条件是 1 > |p - y|。这要求 p 和 y 是相邻的整数，但它们又要互质，这不可能发生（除非一个是1，但我们讨论的是 p>=2）。

素数小结：一个素数 p 是孤独的，当且仅当它的唯一潜在朋友 p^2 不在 1 到 n 的范围内，也就是 p^2 > n，即 p > sqrt(n)。

情况三：x 是一个合数 c 合数会孤独吗？猫娘的直觉是不会！我们来证明一下，任何一个合数 c 都能找到朋友。

  • 令 p 是 c 的最小质因数。那么 c 可以写成 c = p * k，其中 k >= p。
  • 我们来为 c 构造一个朋友 y。一个好的想法是找一个和 c "结构相似" 的数。
  • 试试 y = c - p = p * (k-1)。
    • 因为 c 是合数，k >= p >= 2，所以 k-1 >= 1，y = p(k-1) >= p >= 2。所以 y 是一个合法的、小于 c 的数。
    • g = gcd(c, y) = gcd(pk, p(k-1)) = p * gcd(k, k-1) = p * 1 = p。
    • c' = c/g = k。
    • y' = y/g = k-1。
    • 朋友条件是 g > |c' - y'|，也就是 p > |k - (k-1)| = 1。
    • 因为 p 是质数，所以 p >= 2，p > 1 恒成立！
  • 我们还需要检查另外两个三角不等式：
    • g + y' > c' => p + (k-1) > k => p > 1，成立。
    • c' + y' > g => k + (k-1) > p => 2k-1 > p。因为 k >= p，所以 2k-1 >= 2p-1。而 2p-1 > p (即p>1) 对所有质数成立。所以这个也成立！

太棒啦！我们证明了，对于任何合数 c，c-p (其中p是c的最小质因子) 都是它的朋友！所以，所有合数都不是孤独的！

最终结论！ ​

梳理一下我们的发现：

  1. 数字 1 永远是孤独的。
  2. 素数 p，如果 p > sqrt(n)，它就是孤独的。
  3. 素数 p，如果 p <= sqrt(n)，它不是孤独的（朋友是 p^2）。
  4. 所有合数都不是孤独的。

所以，孤独数字的总数 = 1 (来自数字1) + (满足 sqrt(n) < p <= n 的素数 p 的数量)。

这个问题瞬间就转化成了一个数素数的问题！我们可以用 (n以内素数的总数) - (sqrt(n)以内素数的总数) 来计算后半部分。

为了快速回答多组查询，我们可以预处理出 1 到 10^6 范围内的所有素数，并计算一个素数前缀和数组 prime_counts[i]，表示 1 到 i 之间素数的数量。这样每次查询 n，答案就是 1 + prime_counts[n] - prime_counts[floor(sqrt(n))]，可以在 O(1) 时间内搞定！

AC代码奉上喵~ ​

cpp
#include <iostream>
#include <vector>
#include <cmath>

// 题目 n 的最大值是 10^6，我们开一个稍大一点的数组，喵~
const int MAX_N = 1000001;

// is_prime[i] 用来标记 i 是不是素数
std::vector<bool> is_prime(MAX_N, true);
// prime_counts[i] 用来存 1 到 i 之间素数的总个数（前缀和）
std::vector<int> prime_counts(MAX_N, 0);

// 使用埃氏筛法 (Sieve of Eratosthenes) 预处理出所有素数
void sieve() {
    is_prime[0] = is_prime[1] = false; // 0 和 1 都不是素数哦
    for (int p = 2; p * p < MAX_N; ++p) {
        // 如果 p 是素数
        if (is_prime[p]) {
            // 那么 p 的所有倍数都不是素数，把它们筛掉
            for (int i = p * p; i < MAX_N; i += p)
                is_prime[i] = false;
        }
    }
}

// 预处理素数的前缀和
void precompute_prime_counts() {
    prime_counts[0] = 0;
    for (int i = 1; i < MAX_N; ++i) {
        // 当前的前缀和等于前一个数的前缀和...
        // ...如果当前数是素数，就再加 1
        prime_counts[i] = prime_counts[i - 1] + (is_prime[i] ? 1 : 0);
    }
}

int main() {
    // 加速输入输出，让程序跑得飞快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    // 在处理查询前，先把筛法和前缀和都跑一遍
    sieve();
    precompute_prime_counts();

    int t;
    std::cin >> t;
    while (t--) {
        int n;
        std::cin >> n;

        // 根据我们的推导，孤独数字的数量是：
        // 1 (代表数字1)
        // + (n以内的素数数量)
        // - (sqrt(n)以内的素数数量)
        // 这就等于 1 + (pi(n) - pi(floor(sqrt(n)))) 啦
        
        // 计算 floor(sqrt(n))
        int s = static_cast<int>(sqrt(n));
        // 利用前缀和数组 O(1) 计算答案
        int ans = 1 + prime_counts[n] - prime_counts[s];
        std::cout << ans << "\n";
    }

    return 0;
}

时空复杂度分析的说~ ​

  • 时间复杂度: O(MAX_N * log(log(MAX_N)) + T) 的说。

    • 埃氏筛法的时间复杂度是 O(MAX_N * log(log(MAX_N)))。
    • 预处理前缀和数组是 O(MAX_N)。
    • 这两部分是一次性的预处理。之后对于 T 次查询，每次查询都只需要 O(1) 的时间。
    • 所以总时间就是预处理的时间加上所有查询的时间。

  • 空间复杂度: O(MAX_N) 的说。

    • 我们需要两个大小为 MAX_N 的数组 is_prime 和 prime_counts 来存储预处理的结果。

猫娘的小课堂~ ​

这道题真是太有意思啦！它教会了我们几件重要的事情：

  1. 化繁为简: 不要被题目复杂的定义吓到！"朋友" 关系看起来很复杂，但通过数学分析，我们把它简化成了一个非常清晰的不等式 g > |a' - b'|。
  2. 分类讨论是好朋友: 当你对一个问题没有头绪时，尝试把研究对象（这里的数字 x）根据它的性质（是1，是素数，还是合数）进行分类，往往能让思路豁然开朗！
  3. 构造的力量: 在证明所有合数都不是孤独的时候，我们通过构造一个特定的朋友 y = c - p 来完成了证明。这种构造性的证明方法在数论和组合数学里非常有用哦。
  4. 预处理大法好: 对于有多组查询，并且查询范围固定的问题，一定要想到预处理！通过一次性的计算，把之后每次查询的复杂度降到最低，是竞赛中超级实用的技巧。

总之，这道题完美地结合了数论分析和算法技巧。希望通过本猫娘的讲解，你也感受到了解决它的乐趣！下次遇到类似的题目，也要像这样勇敢地去分析和拆解哦！加油喵~ 💖

Released under the MIT License.

Copyright © 2024-present Moe