第三心脏 - 题解

标签与难度

标签: 数论, 最大公约数, GCD, 质因数分解, 构造难度: 1600

题目大意喵~

主人你好呀，这道题是关于寻找一个特殊的数字c的，喵~ 题目给了我们两个正整数 $a$ 和 $b$ ，需要我们找到一个最小的正整数 $c$ ，它要满足下面两个条件哦：

$c$ 必须是 $a$ 的倍数，而且要比 $a$ 大，也就是 $c > a$ 。
$(a, b)$ 的最大公约数要和 $(b, c)$ 的最大公约数相等，写成数学的样子就是 $\gcd(a, b) = \gcd(b, c)$ 。

简单来说，就是要在 $2a, 3a, 4a, \dots$ 这些数里面，找到第一个让 $\gcd(b, c)$ 和 $\gcd(a, b)$ 相等的 $c$ 啦！

解题思路分析

这道题看起来有点数学呢，不过别怕，跟着我的思路一步一步来，很快就能找到线索的，喵~

第一步：把问题变个形状

首先，我们来看题目给的两个条件。

第一个条件说， $c$ 是 $a$ 的倍数且 $c > a$ 。这不就意味着 $c$ 可以被写成 $c = k \cdot a$ 的形式嘛？其中 $k$ 是一个大于 1 的整数，也就是 $k \in \{2, 3, 4, \dots\}$ 。我们的目标就是找到满足条件的、最小的那个 $c$ ，这等价于找到最小的那个整数 $k \ge 2$ 。

第二个条件是核心， $\gcd(a, b) = \gcd(b, c)$ 。我们把 $c = k \cdot a$ 代入这个式子，就得到：

\gcd(a, b) = \gcd(b, k \cdot a)

第二步：引入最大公约数 g

为了让这个式子更清晰，我们引入一个很重要的角色—— $a$ 和 $b$ 的最大公约数！我们叫它 $g$ 好了，即 $g = \gcd(a, b)$ 。

根据最大公约数的定义，我们可以把 $a$ 和 $b$ 表示成：

$a = g \cdot a'$
$b = g \cdot b'$

这里的 $a'$ 和 $b'$ 是两个非常好的孩子，它们是互质的，也就是说 $\gcd(a', b') = 1$ 。这一点非常非常关键哦！

现在，我们把 $a = g \cdot a'$ 和 $b = g \cdot b'$ 代入我们之前的等式：

g = \gcd(g \cdot b', k \cdot g \cdot a')

第三步：神奇的化简！

这里有一个超有用的GCD性质： $\gcd(m \cdot x, m \cdot y) = m \cdot \gcd(x, y)$ 。我们可以把等式右边的公共因子 $g$ 提出来！

g = g \cdot \gcd(b', k \cdot a')

两边都有 $g$ ，我们可以把它约掉（因为 $g$ 是正整数嘛），就得到了一个超级清爽的式子：

1 = \gcd(b', k \cdot a')

这个式子的意思是， $b'$ 和 $k \cdot a'$ 必须互质。我们已经知道 $\gcd(a', b') = 1$ 了，所以 $a'$ 和 $b'$ 之间没有任何共同的质因数。要让 $k \cdot a'$ 和 $b'$ 互质，就只需要保证 $k$ 和 $b'$ 互质就行啦！

所以，问题最终被我们转化成： 找到一个最小的整数 $k \ge 2$ ，使得 $\gcd(b', k) = 1$ ，其中 $b' = b / \gcd(a, b)$ 。

第四步：k 究竟是谁呢？

现在问题变得好简单了！我们只需要找到最小的 $k \ge 2$ 并且和 $b'$ 互质。

我在这里有一个小小的洞察，喵~ 这个最小的 $k$ 一定是一个质数！为什么呢？我们可以用反证法想一下：假设我们找到的最小的 $k$ 是一个合数，比如 $k = p \cdot m$ （其中 $p$ 是 $k$ 的最小质因数）。因为 $\gcd(b', k) = 1$ ，所以 $b'$ 和 $k$ 没有共同的质因数。那么 $b'$ 和 $p$ 肯定也没有共同的质因数，即 $\gcd(b', p) = 1$ 。但是！因为 $p$ 是 $k$ 的一个因数，所以 $p < k$ 。这下就矛盾啦！我们找到了一个比 $k$ 更小的数 $p$ （ $p \ge 2$ 因为 $k \ge 2$ ），它也和 $b'$ 互质。这和我们“ $k$ 是最小的”这个假设矛盾了。所以，我们的假设是错的！最小的 $k$ 一定是一个质数，喵呜~

最终的算法！

所以我们的最终策略就是：

计算 $g = \gcd(a, b)$ 。
计算 $b' = b / g$ 。
找到最小的那个质数 $p$ ，使得 $p$ 不是 $b'$ 的因数（也就是说 $b' \pmod p \neq 0$ ）。这个质数 $p$ 就是我们梦寐以求的 $k$ ！
最终的答案 $c$ 就是 $a \cdot p$ 。

怎么找到这个最小的质数 $p$ 呢？我们可以先分解 $b'$ 的质因数，把它们都记下来。然后从最小的质数 2, 3, 5, ... 开始检查，第一个不在 $b'$ 的质因数集合里的质数，就是我们要找的啦！

举个例子： $a=7, b=42$

$g = \gcd(7, 42) = 7$ 。
$b' = 42 / 7 = 6$ 。
$6$ 的质因数是 $\{2, 3\}$ 。
我们来找最小的、不在这里面的质数：
- 是 2 吗？不是，2 在里面。
- 是 3 吗？不是，3 在里面。
- 是 5 吗？是的！5 不在 $\{2, 3\}$ 里面。
所以我们找到了 $k=5$ 。答案 $c = a \cdot k = 7 \cdot 5 = 35$ 。验证一下： $\gcd(7, 42) = 7$ ， $\gcd(42, 35) = 7$ 。完美！

代码实现

下面就是我根据这个思路精心编写的代码啦，注释写得很详细，希望能帮到主人哦~

cpp

#include <iostream>
#include <numeric> // 需要用 std::gcd
#include <set>     // 用来存放质因数，喵~

// 一个帮助我们解决单个测试用例的函数
void solve() {
    long long a, b;
    std::cin >> a >> b;

    // 第一步：计算 g = gcd(a, b)
    long long g = std::gcd(a, b);

    // 第二步：计算 b' = b / g
    long long b_prime = b / g;

    // 如果 b' 等于 1，说明 b 是 a 的倍数。
    // 此时 gcd(b', k) = gcd(1, k) = 1 对于任何 k 都成立。
    // 我们要找最小的 k >= 2，那自然就是 2 啦！
    if (b_prime == 1) {
        std::cout << a * 2 << std::endl;
        return;
    }

    // 第三步：找到 b' 的所有质因数
    // 用一个 set 来存储，可以自动去重，很方便喵~
    std::set<long long> prime_factors;
    long long temp_b = b_prime;

    // 先处理因数 2
    if (temp_b % 2 == 0) {
        prime_factors.insert(2);
        while (temp_b % 2 == 0) {
            temp_b /= 2;
        }
    }

    // 再处理从 3 开始的奇数因数
    for (long long i = 3; i * i <= temp_b; i += 2) {
        if (temp_b % i == 0) {
            prime_factors.insert(i);
            while (temp_b % i == 0) {
                temp_b /= i;
            }
        }
    }

    // 如果最后 temp_b 还大于 1，说明它本身也是一个大质因数
    if (temp_b > 1) {
        prime_factors.insert(temp_b);
    }

    // 第四步：找到最小的、不属于 b' 质因数集合的质数
    long long k = 2; // 我们要找的最小 k

    // 先看看 2 是不是 b' 的质因数
    if (prime_factors.find(2) == prime_factors.end()) {
        k = 2;
    } else {
        // 如果 2 是，就从 3 开始找下一个质数
        // 因为我们已经证明了 k 必须是质数，所以可以只检查奇数
        for (long long p = 3; ; p += 2) {
            // 我们只需要找第一个不被 b' 整除的质数 p
            // 实际上，因为 p 是递增的质数，它肯定不在 b' 的质因数集合中
            if (b_prime % p != 0) {
                k = p;
                break;
            }
        }
    }

    // 最终答案 c = a * k
    std::cout << a * k << std::endl;
}

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

    int T; // 数据组数
    std::cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

复杂度分析

时间复杂度: $O(\sqrt{b/g})$ 对于每个测试用例，主要的时间开销在于对 $b' = b/\gcd(a, b)$ 进行质因数分解。试除法分解一个数 $N$ 的时间复杂度是 $O(\sqrt{N})$ 。找到最小非因数质数的过程非常快，因为这个质数通常很小。所以总的时间复杂度是 $O(\sqrt{b/g})$ 。
空间复杂度: $O(\log(b/g))$ 我们使用了一个 std::set 来存储 $b'$ 的质因数。一个数 $N$ 的不同质因数的数量级是 $O(\log N)$ 。对于 long long 范围内的数，不同质因数的数量非常少（最多十几个），所以空间占用几乎是常数级别的，喵~

知识点总结

这道题是数论知识的一次美妙应用，我们用到了：

最大公约数 (GCD) 的性质: 核心是 $\gcd(m \cdot x, m \cdot y) = m \cdot \gcd(x, y)$ ，这个性质帮助我们大大简化了问题。
互质关系: 理解了 $\gcd(x, y \cdot z) = 1$ 当且仅当 $\gcd(x, y) = 1$ 且 $\gcd(x, z) = 1$ 。
质因数分解: 这是找到一个数有哪些质数"基因"的常用方法。
构造性证明: 通过简单的反证法，我们得出了最小的 $k$ 一定是质数这个漂亮的结论，这让我们的搜索目标变得非常明确。

希望这篇题解能帮助主人更好地理解这道题，如果还有问题，随时可以再来问我哦！喵~

第三心脏 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

第一步：把问题变个形状 ​

第二步：引入最大公约数 g ​

第三步：神奇的化简！ ​

第四步：k 究竟是谁呢？ ​

最终的算法！ ​

代码实现 ​

复杂度分析 ​

知识点总结 ​