小红的完全平方数

import java.io.*;
import java.util.*;
public class Test3 {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        String s = reader.readLine();
        int n = Integer.parseInt(s);
        String s1 = reader.readLine();
        String[] split = s1.split(" ");
        int[] t = new int[n];
        for (int i = 0; i < split.length; i++) {
            t[i] = Integer.parseInt(split[i]);
        }
        writer.write(getMinNumber(t) + "\n");
        writer.close();
        reader.close();
    }

    /**
     * * 首先定义一个方法，用来计算最简的公共因子。
     * 最简公共因子不会出现成对的质因数。
     * 例如 4 = 2 * 2,化简后变成了1，两个2消除掉
     * 18= 2*3*3 化简后两个2消除掉变成3.
     * 50 = 2*5*5 化简后变成了2，两个5消除了
     * f(4)=1,f(18)=2,f(50)=2
     * <p>
     * 第一步，先找到出现最多的公共因子。
     * 第二步，统计公共因子出现次数最多的次数。
     * 第三步，计算结果为数组长度-最大次数
     * <p>
     * 假设化简后数组为【k1,k2,k3,k1,k1】
     * 这里出现最多的因子是k1。
     * 要想把这个队列变成完美队列。只需要统计k1出现的次数。
     * 总数-k1出现的次数就是答案。
     * 相乘后变成【k1,k2*k2*k1,k3*k3*k1,k1,k1】
     * 最少操作2次。
     * 数组长度为5，k1出现了3次。
     * 所以结果为5-3=2.
     */
    public static long getMinNumber(int[] t) {
        //定义一个平方数组，用来作除数，里面存的是2-1000的平方
        int[] arr = new int[999];
        for (int i = 2; i <= 1000; i++) {
            arr[i - 2] = i * i;
        }
        //只有一个或者没有的时候，直接返回0
        for (int i = 0; i < t.length; i++) {
            t[i] = getSimpleNumber(t[i], arr);
        }

        //统计数量最多的因子
        Map<Integer, Integer> map = new HashMap<>();
        int max = 0;
        for (int j : t) {
            int count = map.getOrDefault(j, 0) + 1;
            if (count > max) {
                max = count;
            }
            map.put(j, count);
        }
        //返回数组长度-最多的公共因子的个数
        return t.length - max;
    }

    /**
     * 把一个数拆解成最简单的方式，本来就是平方数的拆解成1
     * 4 = 2*2 这里和1没有区别
     * 18 = 2*3*3 这里拆解成2
     * 24 = 4*6 最后变成6
     *
     * 这里需要注意，一个数可以被除多次，例如36，是4的除数也是9的除数
     * 最后要变成1
     */
    public static int getSimpleNumber(int n, int[] arr) {
        boolean flag = true;
        while (flag) {
            for (int i = 0; i < arr.length; i++) {
                if (n % arr[i] == 0) {
                    n /= arr[i];
                    break;
                }
                //当N都开始小于j,就不可能整除了
                if (n < arr[i]) {
                    flag = false;
                    break;
                }
                //走到了最后
                if (i == arr.length - 1) {
                    flag = false;
                }
            }
        }
        return n;
    }


}

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

const int MAXA = 1e6+5;

int spf[MAXA]; // 最小质因子表

// 线性筛求最小质因子
void sieve() {
    for (int i = 2; i < MAXA; ++i) spf[i] = 0;
    for (int i = 2; i < MAXA; ++i) {
        if (spf[i] == 0) {
            spf[i] = i;
            if ((long long)i * i < MAXA) {
                for (int j = i * i; j < MAXA; j += i) {
                    if (spf[j] == 0) spf[j] = i;
                }
            }
        }
    }
}

// 这里用vector存奇质因子，返回一个字符串方便哈希
string getOddPrimeSignature(int x) {
    unordered_map<int,int> cnt;
    while (x > 1) {
        int p = spf[x];
        cnt[p]++;
        x /= p;
    }
    vector<int> factors;
    for (auto &kv : cnt) {
        if (kv.second % 2 == 1) factors.push_back(kv.first);
    }
    sort(factors.begin(), factors.end());
    string res;
    for (int p : factors) res += to_string(p) + ",";
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    sieve();

    int n; cin >> n;
    vector<int> a(n);
    for (int i=0; i<n; i++) cin >> a[i];

    unordered_map<string,int> freq;
    for (int x : a) {
        string sig = getOddPrimeSignature(x);
        freq[sig]++;
    }

    int maxFreq = 0;
    for (auto &kv : freq) {
        maxFreq = max(maxFreq, kv.second);
    }

    cout << n - maxFreq << "\n";

    return 0;
}