小M的数组变换

题目背景

我们手头有一个整数数组，小M可以通过以下操作来改变数组中的元素：

1. 选择数组中的两个元素 ai 和 aj；
2. 选择 ai 的一个因子 x，然后将 ai 变为 ai / x，同时将 aj 变为 aj×x。

她的目标是使得数组中的每个元素最终只包含一种素因子，例如 4 的素因子是 2，目标就是将其改造成 2^n 的形式。如果操作次数不限，我们需要判断能否实现这个目标。

题目分析

素因子：一个数的素因子是其质因数。

操作的本质：通过不断地将素因子从一个元素转移到另一个元素，使得每个元素最终只剩一种素因子。

关键点：如果数组中的素因子种类数小于等于数组的长度 n，则可以通过操作实现目标；如果素因子种类数超过数组长度 n，则无法完成。

解题思路

我们需要解决以下几个核心问题：

1. 如何计算素因子种类：
   • 遍历数组中的每个数字，对其进行素因数分解，提取所有的素因子。
   • 通过 Set 数据结构记录所有的素因子，避免重复。
2. 如何判断是否满足条件：
   • 统计所有素因子的种类数，若种类数小于等于 n，输出 "Yes"；否则输出 "No"。
3. 实现逻辑流程：
   • 使用一个辅助函数对数字进行素因数分解。
   • 遍历数组，提取所有数字的素因子并存入集合中。
   • 最后根据集合的大小判断是否满足条件。

算法实现（Java）

以下是问题的 Java 实现代码：

import java.util.*;

public class Solution {

    /**
     * 判断是否能将数组变为每个元素只包含一种素因子的形式
     * @param n 数组长度
     * @param a 数组
     * @return "Yes" 或 "No"
     */
    public static String canTransform(int n, int[] a) {
        // 用 Set 存储所有素因子
        Set<Integer> primeFactors = new HashSet<>();

        // 遍历数组中的每个元素
        for (int x : a) {
            // 对当前元素进行素因数分解
            for (int i = 2; i * i <= x; i++) { // 从 2 开始遍历到 sqrt(x)
                if (x % i == 0) { // 如果 i 是 x 的因子
                    primeFactors.add(i); // 将 i 加入素因子集合
                    while (x % i == 0) { // 去除 x 中所有的 i 因子
                        x /= i;
                    }
                }
            }
            // 如果 x 本身是一个大于 1 的素数
            if (x > 1) {
                primeFactors.add(x);
            }
        }

        // 判断素因子的种类是否不超过 n
        return primeFactors.size() <= n ? "Yes" : "No";
    }

    public static void main(String[] args) {
        // 测试样例
        int[] a1 = {1, 2, 3, 4};
        int[] a2 = {10, 12};
        int[] a3 = {6, 9, 15};

        System.out.println(canTransform(4, a1)); // 输出：Yes
        System.out.println(canTransform(2, a2)); // 输出：No
        System.out.println(canTransform(3, a3)); // 输出：Yes
    }
}

代码解析

1. 素因数分解：
   • 对于每个数字 x，从 2 开始尝试，逐步提取因子 i，直到 i×i>x 。
   • 对于提取出的每个因子，将其加入到 Set 中，同时不断除去该因子，确保不会重复记录。
   • 最后若 x>1，说明 x 本身是素数，将其直接加入集合。
2. 判断条件：
   • 使用 Set 的 size() 方法获取素因子种类数。

算法复杂度分析

1. 时间复杂度：
   • 对于每个数组元素 x，素因数分解的复杂度为 O(x)O(sqrt{x})。
   • 数组长度为 n，总复杂度为 O(n×数组中最大值开方)。
2. 空间复杂度：
   • 使用 Set 存储素因子，最坏情况下复杂度为 O(素因子种类数)。

测试结果

运行代码后，输出如下：

Yes
No
Yes

测试结果符合预期，代码逻辑正确。

总结

通过素因数分解和集合统计，我们可以高效判断数组是否能通过操作达到目标。本题的核心在于理解素因数分解的原理以及操作对素因子转移的影响，结合 Java 的集合类，代码实现简洁高效。

本方法不仅可以解决本题，还为理解素因数分解提供了通用框架，是数学与编程结合的典范问题之一。

博客主页: 总是学不会.