喵~ 主人，下午好呀！Gellyfish 的数学作业看起来有点绕脑筋呢，不过别担心，有本猫娘在，再复杂的问题也能理得清清楚楚！就让本猫娘来带你一步步拆解这道题吧，喵~

题目大意

这道题是说呀，我们有一个装着 n 个正整数的数组 a。我们可以进行一种操作：选两个不同的下标 i 和 j，然后把 a[i] 换成 gcd(a[i], a[j])。我们的目标是，通过若干次这样的操作，让数组里所有的数都变得一模一样。题目问我们，最少需要多少次操作才能达成目标呢？

举个栗子，如果数组是 [12, 20, 30]：

1. 我们可以把 a[3] 变成 gcd(30, 20) = 10，数组就成了 [12, 20, 10]。
2. 再把 a[1] 变成 gcd(12, 10) = 2，数组就成了 [2, 20, 10]。
3. 然后把 a[2] 变成 gcd(20, 2) = 2，数组就成了 [2, 2, 10]。
4. 最后把 a[3] 变成 gcd(10, 2) = 2，数组就成了 [2, 2, 2]。 这样总共花了 4 步，所有数都变成了 2，任务完成啦！

题解方法

要解决这个问题，我们得先像小猫探路一样，小心翼翼地分析几个关键点，喵~

1. 最终的数字是什么？gcd 操作有一个特性，就是 gcd(x, y) <= min(x, y)。这意味着每次操作，数组里的数要么不变，要么变小。那么最后所有数都变成的那个相同的数，我们叫它 g_final 吧，它一定能整除所有原始的数字。为了让操作次数最少，我们应该让 g_final 尽可能大，这样它离原始数字“更近”。所以，最理想的 g_final 就是整个初始数组 a 的所有元素的最大公约数（Greatest Common Divisor, GCD），我们把它记为 g。

2. 如何达成目标？ 我们的策略可以分成两步：

   • 第一步：创造 g。 我们需要在数组中至少一个位置上得到 g。
   • 第二步：传播 g。 一旦我们有了一个 g（比如在 a[k] 的位置），我们就可以用它去“感染”其他所有元素。对于任意 a[i] (其中 i != k)，我们执行操作 a[i] = gcd(a[i], a[k])。因为 g 是所有初始元素的公约数，所以 g 也一定能整除任何操作中途产生的 a[i]，所以 gcd(a[i], g) 的结果就是 g！这样，把 n-1 个其他元素都变成 g，需要 n-1 次操作。

3. 分情况讨论 现在问题就清晰多啦！我们只需要考虑如何最低成本地完成第一步——“创造 g”。这里有两种情况，就像猫咪看到逗猫棒和看到小鱼干一样，反应是不一样的哦！

   • 情况一：初始数组里已经有 g 了。 太棒啦！就像出门就捡到小鱼干一样幸运！我们不需要“创造”g 了。如果初始数组里有 k 个 g，我们只需要把剩下的 n-k 个数变成 g 就行了。这需要 n-k 次操作。

   • 情况二：初始数组里没有 g。 这就需要我们自己动手，丰衣足食了。我们需要从初始数组里选出一个子集，让这个子集的 gcd 等于 g。假设我们选了 m 个数 {b_1, b_2, ..., b_m}，它们的 gcd 是 g。我们可以通过 m-1 次操作（比如 b_1 = gcd(b_1, b_2), b_1 = gcd(b_1, b_3), ...）在 b_1 的位置上得到 g。 为了让总操作数最少，我们需要找到最小的 m。找到这个最小的 m 之后，总操作数就是 (m-1) (创造 g 的成本) + (n-1) (传播 g 的成本) = m + n - 2。

     那么，如何找到这个最小的 m 呢？这就要用到我们聪明的**动态规划（DP）**啦！

题解

好啦，思路清晰了，我们来看看具体的代码实现是怎么做的吧，喵~

1. 计算全局GCD g 首先，读入数据，然后遍历一遍数组，计算出所有数的最大公约数 g。同时，用一个 counts 数组记录一下每个数字出现的次数，后面会用到。

2. 处理情况一 检查一下 counts[g]是不是大于 0。如果是，说明初始数组里就有 g，直接输出 n - counts[g] 就好啦。

3. 处理情况二（DP登场！） 如果初始数组里没有 g，我们就需要用 DP 来找到最小的 m。

   • 定义 DP 状态: dp[x] 表示，从初始数组中选出若干个数，使得它们的 gcd 为 x，所需的最少数字个数。
   • 初始化:
     • 创建一个 dp 数组，大小为数值上限（比如 5001），所有值初始化为一个很大的数（表示无穷大，即当前还无法凑出）。
     • 遍历初始数组中所有不重复的数 v，设置 dp[v] = 1。因为一个数自己和自己的 gcd 就是它本身，所以用 1 个数就能凑出它自己。
   • 状态转移: 这是最核心的一步！我们要想办法用已知的 dp 值来更新其他的 dp 值。 我们可以遍历所有可能的 gcd 值 i（从大到小遍历可以保证我们用到 dp[i] 时它已经是最终值了）。 如果 dp[i] 不是无穷大（说明我们已经知道如何用 dp[i] 个数凑出 gcd 为 i），我们就再从初始数组里选一个不重复的数 v，计算 new_g = gcd(i, v)。 现在，我们用 dp[i] 个数凑出了 i，再加一个 v，总共用了 dp[i] + 1 个数，凑出了 new_g。所以，我们可以更新 dp[new_g]： dp[new_g] = min(dp[new_g], dp[i] + 1)
   • 最终答案: 通过上面的 DP 过程，我们就能计算出 dp[g] 的值，这就是我们梦寐以求的最小 m！ 最终答案就是 dp[g] + n - 2。

下面是带注释的代码，希望能帮主人更好地理解~

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

// 一个求最大公约数的函数，喵~
int custom_gcd(int a, int b) {
    while (b) {
        a %= b;
        std::swap(a, b);
    }
    return a;
}

void solve() {
    int n;
    std::cin >> n;
    const int MAX_A = 5000;
    std::vector<int> a(n);
    std::vector<int> counts(MAX_A + 1, 0); // 用来计数的桶
    int g = 0;

    // 读入数据，同时计算全局GCD和每个数的频率
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
        if (i == 0) {
            g = a[i];
        } else {
            g = custom_gcd(g, a[i]);
        }
        counts[a[i]]++;
    }

    // 情况一：初始数组里已经有g了
    if (counts[g] > 0) {
        std::cout << n - counts[g] << "\n";
        return;
    }

    // 情况二：初始数组里没有g，需要用DP来解决
    const int INF = 1e9; // 表示无穷大
    std::vector<int> dp(MAX_A + 1, INF);

    // 找出所有不重复的初始数字
    std::vector<int> unique_a;
    for(int i = 1; i <= MAX_A; ++i) {
        if (counts[i] > 0) {
            unique_a.push_back(i);
            dp[i] = 1; // DP 初始化：凑出数字i本身只需要1个数
        }
    }

    // DP过程，从大到小遍历所有可能的GCD值
    for (int i = MAX_A; i >= 1; --i) {
        if (dp[i] == INF) { // 如果i都凑不出来，就跳过
            continue;
        }
        // 尝试和每一个初始数字组合
        for (int val : unique_a) {
            int new_g = custom_gcd(i, val);
            // 状态转移方程
            if (dp[i] + 1 < dp[new_g]) {
                dp[new_g] = dp[i] + 1;
            }
        }
    }

    // 最终答案：m + n - 2，这里的m就是dp[g]
    std::cout << dp[g] + n - 2 << "\n";
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

知识点介绍

这道题里藏着两个很重要的知识点哦，就像猫咪的宝藏一样！

1. 最大公约数 (GCD) 最大公约数，也就是 GCD，是能同时整除好几个数的那个最大的正整数。比如 12 和 20 的 gcd 就是 4 啦。求 gcd 最经典的方法就是欧几里得算法，也叫辗转相除法。它的原理是 gcd(a, b) = gcd(b, a % b)。不断重复这个过程，直到其中一个数变成 0，另一个数就是答案。就像猫咪追自己的尾巴一样，转啊转就求出来了，很有趣的！

2. 动态规划 (Dynamic Programming) 动态规划，简称 DP，是一种非常聪明的算法思想，专门用来解决最优化问题。它的核心是**“把大问题分解成小问题，并记录小问题的解，避免重复计算”**。 就像猫咪学捕猎，会把“抓住老鼠”这个大目标分解成“悄悄靠近”、“找准时机”、“猛扑”等小步骤。每一步练习好了，就把技巧记在脑子里，下次就能用得更熟练。DP 就是这样，先解决小规模的问题，然后利用这些解来构建更大规模问题的解，一步步走向最终答案！在这道题里，我们就是先解决“如何用少数几个数凑出某个 gcd”的小问题，然后一步步推导出“如何凑出最终目标 g”的答案。

好啦，这道题的讲解就到这里啦！主人学会了吗？喵~ 如果还有不懂的地方，随时可以再来问我哦！本猫娘随时待命！