小红的完全平方数

[题目链接](https://www.nowcoder.com/practice/8e83151b7a5b4e1196eb9aa4c4ff7d95)

思路

数组是"好数组"当且仅当任意两个元素的乘积都是完全平方数。每次操作可以选一个元素乘以任意正整数，求最少操作次数。

核心观察：无平方因子部分

对于正整数 $x$ ，将其质因数分解为 $x = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$ ，定义 $x$ 的无平方因子部分（square-free part）为：

$ $\text{sf}(x) = \prod_{e_i \bmod 2 = 1} p_i$ $

即保留所有指数为奇数的质因子，各取一次。例如 $\text{sf}(12) = \text{sf}(2^2 \cdot 3) = 3$ ， $\text{sf}(4) = \text{sf}(2^2) = 1$ 。

关键性质：两个正整数 $a, b$ 的乘积 $a \cdot b$ 是完全平方数，当且仅当 $\text{sf}(a) = \text{sf}(b)$ 。

证明： $a \cdot b$ 是完全平方数等价于 $a \cdot b$ 的所有质因子指数均为偶数。对每个质因子 $p$ ，设 $a$ 中指数为 $\alpha$ ， $b$ 中指数为 $\beta$ ，则需要 $\alpha + \beta$ 为偶数，即 $\alpha$ 和 $\beta$ 奇偶性相同。这恰好就是 $\text{sf}(a) = \text{sf}(b)$ 。

贪心策略

数组是好数组当且仅当所有元素的无平方因子部分相同。将每个元素乘以某个正整数可以任意改变其无平方因子部分，因此每次操作恰好能"修正"一个元素。

为使操作次数最少，应保留出现次数最多的那组无平方因子部分不动，将其余元素各操作一次：

$ $\text{ans} = n - \max_{v} \text{count}(\text{sf} = v)$ $

计算无平方因子部分

对每个 $a_i$ ，试除 $2 \sim \sqrt{a_i}$ 的所有质因子，统计每个质因子出现次数的奇偶性。若某个质因子出现奇数次，则乘入 $\text{sf}$ 。试除结束后若剩余值大于 $1$ ，说明有一个大质因子，也乘入 $\text{sf}$ 。

复杂度

时间复杂度： $O(n\sqrt{V})$ ，其中 $V$ 为元素的最大值。每个元素的试除法需 $O(\sqrt{V})$ 。
空间复杂度： $O(n)$ ，用于哈希表存储无平方因子部分的计数。

代码

C++
Java

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    scanf("%d", &n);
    map<long long, int> cnt;
    int zeros = 0;
    for(int i = 0; i < n; i++){
        long long x;
        scanf("%lld", &x);
        if(x == 0){
            zeros++;
            continue;
        }
        if(x < 0) x = -x;
        long long sf = 1;
        for(long long p = 2; p * p <= x; p++){
            int c = 0;
            while(x % p == 0){
                x /= p;
                c++;
            }
            if(c % 2 == 1) sf *= p;
        }
        if(x > 1) sf *= x;
        cnt[sf]++;
    }
    int mx = 0;
    for(auto& [k, v] : cnt){
        mx = max(mx, v);
    }
    int nonzeros = n - zeros;
    int ans = nonzeros - mx;
    printf("%d\n", ans);
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Map<Long, Integer> cnt = new HashMap<>();
        int zeros = 0;
        for (int i = 0; i < n; i++) {
            long x = sc.nextLong();
            if (x == 0) {
                zeros++;
                continue;
            }
            if (x < 0) x = -x;
            long sf = 1;
            for (long p = 2; p * p <= x; p++) {
                int c = 0;
                while (x % p == 0) {
                    x /= p;
                    c++;
                }
                if (c % 2 == 1) sf *= p;
            }
            if (x > 1) sf *= x;
            cnt.merge(sf, 1, Integer::sum);
        }
        int mx = 0;
        for (int v : cnt.values()) {
            mx = Math.max(mx, v);
        }
        int nonzeros = n - zeros;
        int ans = nonzeros - mx;
        System.out.println(ans);
    }
}