E - Equal - 题解

标签与难度

标签: 数论, 质因数分解, 筛法, 不变量, 构造, 哈希 难度: 1800

题目大意喵~

你好呀，未来的算法大师！本喵今天带来了一道有趣的数论题哦~

题目是这样的：Yuki给了我们一个长度为 $n$ 的正整数序列 $a_1, a_2, \ldots, a_n$。我们可以对这个序列进行两种操作，次数不限：

1. 除法操作: 选定两个不同的下标 $i, j$ 和一个正整数 $d$，如果 $d$ 同时是 $a_i$ 和 $a_j$ 的约数，那么我们可以把 $a_i$ 和 $a_j$ 都变成原来的 $\frac{1}{d}$。也就是 $a_i \leftarrow a_i/d$，$a_j \leftarrow a_j/d$。
2. 乘法操作: 选定两个不同的下标 $i, j$ 和一个任意正整数 $d$，我们可以把 $a_i$ 和 $a_j$ 都乘上 $d$。也就是 $a_i \leftarrow a_i \cdot d$，$a_j \leftarrow a_j \cdot d$。

我们的任务是判断，通过这些操作，能不能让序列中所有的数都变得相等呢？如果可以，就输出 "YES"，不然就输出 "NO"，喵~

解题思路分析

这道题看起来操作很灵活，让人有点摸不着头脑，对吧？别怕别怕，让本喵带你一步步解开它的神秘面纱！处理这类问题，一个超好用的技巧就是寻找 不变量 或者 半不变量，也就是在操作过程中保持不变或者变化有规律的性质，呐。

发现不变量！

让我们来分析一下这两个操作对整个序列产生了什么影响。一个很自然的想法是观察所有数的乘积 $P = \prod_{k=1}^n a_k$。

• 对于除法操作，新的乘积 $P'$ 会变成 $(a_i/d) \cdot (a_j/d) \cdot \prod_{k \neq i,j} a_k = \frac{P}{d^2}$。乘积被除以了一个完全平方数 $d^2$。
• 对于乘法操作，新的乘积 $P'$ 会变成 $(a_i \cdot d) \cdot (a_j \cdot d) \cdot \prod_{k \neq i,j} a_k = P \cdot d^2$。乘积被乘上了一个完全平方数 $d^2$。

看到了吗？无论哪种操作，总乘积 $P$ 的变化都是乘以或除以一个完全平方数。这对我们有什么启发呢？

让我们把目光投向质因数分解！任何一个正整数都可以唯一地分解成质数的幂次乘积。 设 $v_p(x)$ 表示正整数 $x$ 的质因数分解中，质数 $p$ 的指数。 那么，整个序列所有数的乘积 $P$ 中，质数 $p$ 的总指数就是 $S_p = \sum_{k=1}^n v_p(a_k)$。

当进行一次操作时，比如 $a_i, a_j$ 同乘或同除 $d$，设 $v_p(d) = c_p$。那么新的总指数 $S'_p$ 会变成： $S'_p = S_p \pm 2c_p$。 重点来啦！$S'_p$ 和 $S_p$ 的差是 $2c_p$，一个偶数！这意味着 $S'_p$ 和 $S_p$ 的奇偶性是完全一样的！

核心不变量: 对于任意一个质数 $p$，它在序列所有数的质因数分解中出现的总次数的奇偶性，是一个不变量！喵~

连接不变量与目标

我们的目标是让所有数都相等，比如说都等于某个值 $X$。如果能做到，那么最终序列就是 $X, X, \ldots, X$。 此时，质数 $p$ 的总指数就是 $n \cdot v_p(X)$。

根据我们的不变量，初始状态和最终状态的质数 $p$ 总指数的奇偶性必须相同。所以，对于每一个质数 $p$，都必须满足下面的同余方程：

$$\sum_{k=1}^n v_p(a_k) \equiv n \cdot v_p(X) \pmod 2$$

现在，我们来分情况讨论 $n$ 的奇偶性，这可是解题的关键转折点哦！

情况一：$n$ 是奇数

当 $n$ 是奇数时，$n \equiv 1 \pmod 2$。上面的条件就变成了：

$$\sum_{k=1}^n v_p(a_k) \equiv v_p(X) \pmod 2$$

这个条件告诉我们，最终目标值 $X$ 中质数 $p$ 的指数 $v_p(X)$ 的奇偶性，必须和初始序列中 $p$ 的总指数的奇偶性一致。 但我们是可以自由选择目标值 $X$ 的呀！所以，我们总可以构造出一个合适的 $X$ 来满足这个奇偶性要求。

那么，只要奇偶性满足，就一定能做到吗？ 当 $n \ge 3$ 时，我们有足够的操作空间。比如我们想把一个因子 $d$ 从 $a_k$ "移动" 到 $a_i$ (前提是 $d|a_k$)，可以这样做：

1. 选 $a_i, a_j$ 进行乘法操作：$a_i \to a_i \cdot d, a_j \to a_j \cdot d$。
2. 选 $a_j, a_k$ 进行除法操作：$a_j \to a_j/d, a_k \to a_k/d$。 两步下来， $a_i$ 变成了 $a_i \cdot d$，$a_k$ 变成了 $a_k/d$，$a_j$ 不变。我们成功地转移了因子！ 这意味着我们可以把所有质因数汇集起来，然后再平均（或者说，以满足奇偶性的方式）分配给每个数。因此，当 $n$ 是奇数时，我们总能做到让所有数相等！ (对于 $n=1$，本来就相等，当然也是 YES 啦) 所以，当 $n$ 是奇数时，答案总是 "YES"。

情况二：$n$ 是偶数

当 $n$ 是偶数时，$n \equiv 0 \pmod 2$。我们的不变量条件变成了：

$$\sum_{k=1}^n v_p(a_k) \equiv n \cdot v_p(X) \equiv 0 \cdot v_p(X) \equiv 0 \pmod 2$$

哇！这意味着，对于每一个质数 $p$，它在初始序列中出现的总次数 $\sum_{k=1}^n v_p(a_k)$ 必须是偶数！ 这是一个非常强的必要条件。如果对于任何一个质数，它的总数是奇数，那就绝对不可能成功，可以直接说 "NO"。

那这个条件是充分的吗？也就是说，只要所有质数的总个数都是偶数，就一定能成功吗？

• 对于 $n \ge 4$ 的偶数：和 $n$ 是奇数时类似，我们有足够的“中间人” $a_j, a_k$ 来帮助我们转移因子。所以只要满足了所有质因数总数为偶数这个条件，我们就能把它们重新分配，最终达成目标。所以答案是 "YES"。
• 对于 $n=2$ 的特殊情况：这时我们只有 $a_1, a_2$。我们无法找到第三个数来当“中间人”。让我们看看操作对 $a_1, a_2$ 的影响：
  • 除法：$a_1/d, a_2/d$。比率 $(a_1/d) / (a_2/d) = a_1/a_2$。
  • 乘法：$a_1 \cdot d, a_2 \cdot d$。比率 $(a_1 \cdot d) / (a_2 \cdot d) = a_1/a_2$。 天哪！它们的比率 $a_1/a_2$ 竟然也是一个不变量！如果要让它们相等，比率必须是1。这意味着，它们从一开始就必须相等！ 所以，当 $n=2$ 时，只有在 $a_1=a_2$ 的情况下答案才是 "YES"。

算法总结

好啦，思路已经非常清晰了，可以总结我们的算法了喵：

1. 读入 $n$ 和序列 $a$。
2. 如果 $n$ 是奇数，直接输出 "YES"。
3. 如果 $n$ 是偶数： a. 如果 $n=2$，判断 $a_1$ 是否等于 $a_2$。是则输出 "YES"，否则 "NO"。 b. 如果 $n \ge 4$ 且是偶数，我们需要统计所有 $a_i$ 的质因数总个数。 i. 用一个 map 或 unordered_map 来记录每个质数的总出现次数。 ii. 遍历序列中的每个数 $a_i$，对它进行质因数分解。对于每个质因子 $p$ 和它的指数 $k$，将 map[p] 的值增加 $k$。 iii. 为了快速分解质因数（因为 $a_i$ 最大有 $5 \cdot 10^6$），我们需要预处理。最高效的方法是使用线性筛或类似方法，预计算出每个数（到 $5 \cdot 10^6$）的最小质因子 (Smallest Prime Factor, SPF)。这样分解一个数的时间复杂度就从 $O(\sqrt{a_i})$ 降到了 $O(\log a_i)$。 iv. 分解完所有数后，检查 map 中所有的值（即每个质数的总指数）。如果发现任何一个是奇数，就输出 "NO"。如果全部是偶数，就输出 "YES"。

搞定！是不是感觉思路一下子就顺畅了？喵~

代码实现

这是本喵根据上面的思路，精心为你准备的一份代码~ 注释超详细的哦！

#include <iostream>
#include <vector>
#include <numeric>
#include <map>

// 最大可能的 a_i 值
const int MAX_A = 5000000;
// 用于存储每个数的最小质因子(Smallest Prime Factor)
std::vector<int> spf(MAX_A + 1);

// 使用筛法预处理[1, MAX_A]范围内所有数的最小质因子
// 这样可以实现O(log n)的快速质因数分解
void sieve() {
    // 初始化，每个数的最小质因子是它自己
    std::iota(spf.begin(), spf.end(), 0);
    for (int i = 2; i * i <= MAX_A; ++i) {
        // 如果i是质数（因为它的spf还是它自己）
        if (spf[i] == i) {
            // 那么i是它所有倍数的质因子
            for (int j = i * i; j <= MAX_A; j += i) {
                // 如果j还没有被标记过更小的质因子
                if (spf[j] == j) {
                    spf[j] = i;
                }
            }
        }
    }
}

// 单个测试用例的处理函数
void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    bool all_same = true;
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
        if (i > 0 && a[i] != a[0]) {
            all_same = false;
        }
    }

    // 情况一：n是奇数，总是可以的
    if (n % 2 != 0) {
        std::cout << "YES\n";
        return;
    }

    // 情况二：n是偶数
    if (n == 2) {
        // n=2时，只有初始就相等才行
        if (all_same) {
            std::cout << "YES\n";
        } else {
            std::cout << "NO\n";
        }
        return;
    }

    // n >= 4 且为偶数
    // 统计所有质因子的总数
    std::map<int, int> prime_counts;
    for (int num : a) {
        int temp = num;
        while (temp > 1) {
            prime_counts[spf[temp]]++;
            temp /= spf[temp];
        }
    }

    // 检查每个质因子的总数是否为偶数
    bool possible = true;
    for (auto const& [prime, count] : prime_counts) {
        if (count % 2 != 0) {
            possible = false;
            break;
        }
    }

    if (possible) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

int main() {
    // C++ IO 加速，本喵跑得更快~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    // 在所有测试用例开始前，进行一次预处理
    sieve();

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

    return 0;
}

复杂度分析

• 时间复杂度: $O(M \log \log M + \sum n \log A_{max})$

  • $M$ 是 $a_i$ 的最大值（$5 \cdot 10^6$）。筛法预处理的时间复杂度是 $O(M \log \log M)$。这部分在所有测试用例前只执行一次。
  • 对于每个测试用例，我们需要遍历 $n$ 个数。对每个数 $a_i$ 进行质因数分解，因为我们用了 SPF 数组，所以分解一个数的时间是 $O(\log a_i)$。
  • 所有测试用例的总时间就是 $\sum n \log A_{max}$，其中 $\sum n$ 不超过 $2 \cdot 10^6$。
  • 总体来看，这个效率是完全可以通过的，喵~

• 空间复杂度: $O(M)$

  • 我们主要的额外空间开销是 spf 数组，它的大小是 $M+1$。所以空间复杂度是 $O(M)$。

知识点总结

这道题是数论与算法思维的完美结合，我们可以从中学习到：

1. 不变量思想: 在面对复杂动态过程时，寻找不变量是化繁为简的利器。本题中，质因子总数的奇偶性就是关键的不变量。
2. 质因数分解: 数论问题的基石。对于有范围限制的批量分解任务，预处理（如筛法）是提高效率的不二法门。
3. SPF筛 (Smallest Prime Factor Sieve): 一种高效的筛法变体，能在 $O(M \log \log M)$ 内预处理出范围内所有数的最小质因子，从而实现 $O(\log N)$ 的快速查询式分解。
4. 分类讨论: 根据问题性质（本题是 $n$ 的奇偶性）进行分类讨论，常常能让问题结构变得清晰。
5. 特殊情况处理: 不要忘记检查算法的边界和特殊情况，比如本题中的 $n=2$。

希望这篇题解能帮到你！如果还有不明白的地方，随时可以来问本喵哦~ 祝你刷题愉快，早日成为大牛！喵~