题解 | #小红的完全平方数#

题目链接

小红的完全平方数

题目描述

给定一个长度为 $n$ 的整数数组。如果数组中任意两个数 $a_i, a_j$ 的乘积都是完全平方数，则称该数组为“好数组”。

小红可以执行操作：选择数组中的一个数，将其乘以任意正整数。她想知道，最少需要多少次操作才能使数组变成一个“好数组”。

解题思路

这是一个最优化问题，关键在于将“好数组”的性质转化为一个更易于处理的数学条件。

“好数组”的性质

一个数是完全平方数，当且仅当其所有质因子的指数都是偶数。

考虑两个数 $x$ 和 $y$ 。设它们的质因数分解分别为： $x = p_1^{e_{x1}} \cdot p_2^{e_{x2}} \cdot \dots$ $y = p_1^{e_{y1}} \cdot p_2^{e_{y2}} \cdot \dots$

它们的乘积为： $x \cdot y = p_1^{e_{x1}+e_{y1}} \cdot p_2^{e_{x2}+e_{y2}} \cdot \dots$

要使 $x \cdot y$ 是完全平方数，对于每一个质因子 $p_k$ ，其指数 $e_{xk}+e_{yk}$ 都必须是偶数。这意味着，对于任意一个质因子 $p_k$ ，指数 $e_{xk}$ 和 $e_{yk}$ 的奇偶性必须相同。

这个结论必须对数组中任意两个数都成立。因此，一个数组是“好数组”的充要条件是：数组中所有数字，其每一个质因子的指数，都具有相同的奇偶性。

“无平方因子核心”

我们可以对每个数提取其“本质”部分。任何一个正整数 $a$ 都可以唯一地表示为 $a = s \cdot k^2$ ，其中 $s$ 是一个无平方因子数（square-free number），即 $s$ 的任何质因子指数都为 1。我们称 $s$ 为 $a$ 的**“无平方因子核心”**。

例如：

$12 = 3 \cdot 2^2$ ，核心是 $3$ 。
$18 = 2 \cdot 3^2$ ，核心是 $2$ 。
$50 = 2 \cdot 5^2$ ，核心是 $2$ 。
$9 = 1 \cdot 3^2$ ，核心是 $1$ 。

这个核心 $s$ 是由 $a$ 中所有指数为奇数的质因子相乘得到的。

现在，我们用核心来重新审视“好数组”的条件。 $x = \text{core}(x) \cdot k_x^2$ $y = \text{core}(y) \cdot k_y^2$ $x \cdot y = (\text{core}(x) \cdot \text{core}(y)) \cdot (k_x \cdot k_y)^2$

为了使 $x \cdot y$ 是完全平方数， $\text{core}(x) \cdot \text{core}(y)$ 必须是完全平方数。由于 $\text{core}(x)$ 和 $\text{core}(y)$ 本身都是无平方因子数，它们的乘积是完全平方数的唯一可能是 $\text{core}(x) = \text{core}(y)$ 。

因此，“好数组”的条件等价于：数组中所有数字的“无平方因子核心”都相同。

贪心策略

小红的操作是“乘以一个正整数”。这个操作非常强大，可以把任意一个数 $a_i$ 的核心变为任意我们想要的目标核心 $T$ 。例如，要将 core(a_i) 变为 $T$ ，只需将 $a_i$ 乘以 $p = \text{core}(a_i) \cdot T$ 即可。

我们的目标是让所有数的核心都相同，且操作次数最少。这等价于，我们选择一个目标核心 $T$ ，然后保留所有核心已经是 $T$ 的数，只修改那些核心不是 $T$ 的数。为了让修改的数最少，我们应该选择数组中出现次数最多的核心作为我们的目标核心 $T$ 。

算法步骤

计算核心：遍历数组中的每一个数 $a_i$ ，计算出它的“无平方因子核心”。
- 可以通过试除法实现：从 2 开始，到 $\sqrt{a_i}$ ，分解质因子。对于每个质因子，如果其在 $a_i$ 中的指数是奇数，就将其乘入核心值。
统计频率：使用哈希表（map）来统计每个核心值出现的次数。
找出最大频率：遍历哈希表，找到出现次数最多的核心，其频率为 max_freq。
计算答案：我们选择保留这 max_freq 个数，它们无需操作。剩下的 $n - \text{max_freq}$ 个数都需要进行一次操作。因此，最少操作次数就是 $n - \text{max_freq}$ 。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>

using namespace std;

// 计算一个数的无平方因子核心
int get_square_free_core(int n) {
    int core = 1;
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            int count = 0;
            while (n % i == 0) {
                count++;
                n /= i;
            }
            if (count % 2 == 1) {
                core *= i;
            }
        }
    }
    if (n > 1) { // 如果n还有剩余，说明它是一个质数
        core *= n;
    }
    return core;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    map<int, int> core_counts;
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        core_counts[get_square_free_core(a)]++;
    }

    int max_freq = 0;
    if (n > 0) {
        for (auto const& [core, count] : core_counts) {
            if (count > max_freq) {
                max_freq = count;
            }
        }
    }

    cout << n - max_freq << endl;

    return 0;
}

import java.util.Scanner;
import java.util.HashMap;
import java.util.Map;

public class Main {
    // 计算一个数的无平方因子核心
    private static int getSquareFreeCore(int n) {
        int core = 1;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                int count = 0;
                while (n % i == 0) {
                    count++;
                    n /= i;
                }
                if (count % 2 == 1) {
                    core *= i;
                }
            }
        }
        if (n > 1) { // 如果n还有剩余，说明它是一个质数
            core *= n;
        }
        return core;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        Map<Integer, Integer> coreCounts = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt();
            int core = getSquareFreeCore(a);
            coreCounts.put(core, coreCounts.getOrDefault(core, 0) + 1);
        }

        int maxFreq = 0;
        if (n > 0) {
            for (int count : coreCounts.values()) {
                if (count > maxFreq) {
                    maxFreq = count;
                }
            }
        }

        System.out.println(n - maxFreq);
    }
}

import sys
from collections import Counter

def get_square_free_core(n):
    """计算一个数的无平方因子核心"""
    core = 1
    i = 2
    while i * i <= n:
        if n % i == 0:
            count = 0
            while n % i == 0:
                count += 1
                n //= i
            if count % 2 == 1:
                core *= i
        i += 1
    if n > 1:
        core *= n
    return core

def solve():
    n_str = sys.stdin.readline()
    if not n_str: return
    n = int(n_str)
    
    a = list(map(int, sys.stdin.readline().split()))

    if n == 0:
        print(0)
        return

    cores = [get_square_free_core(x) for x in a]
    
    if not cores:
        print(0)
        return
        
    core_counts = Counter(cores)
    max_freq = core_counts.most_common(1)[0][1]
    
    print(n - max_freq)

solve()

算法及复杂度

算法：数论 (质因数分解) + 贪心 + 哈希表
时间复杂度： $O(N \cdot \sqrt{A_{max}})$ 。其中 $N$ 是数组元素的数量， $A_{max}$ 是数组中的最大值。主要开销在于对 $N$ 个数中的每一个都进行一次试除法来计算其“无平方因子核心”，每次计算的时间复杂度为 $O(\sqrt{A_{max}})$ 。
空间复杂度： $O(N)$ 。在最坏情况下，所有 $N$ 个数的核心都不同，哈希表需要存储 $N$ 个条目。