小红的完全平方数

#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;
}