相等序列
1E5以内的质数有 1E4个
每个质数跑1E5次，TLE
#include <bits/stdc++.h>using i64 = long long;std::vector<int> minp, primes;void sieve(int n) {minp.assign(n + 1, 0);primes.clear();for (int i = 2; i <= n; i++) {if (minp[i] == 0) {minp[i] = i;primes.push_back(i);}for (auto p : primes) {if (i * p > n) {break;}minp[i * p] = p;if (p == minp[i]) {break;}}}
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);sieve(1E5 + 5);// std::cout << "primes = " << primes.size() << "\n";// primes = 9593int n;std::cin >> n;std::vector<int> a(n);std::set<int> st;for (int i = 0; i < n; ++i) {std::cin >> a[i];for (int x = a[i]; x != 1; x /= minp[x]) {st.insert(minp[x]);}}int ans = 0;for (int p : primes) {std::vector<int> cnt(20);for (int i = 0; i < n; ++i) {int t = 0;for (int x = a[i]; x % p == 0; x /= p) {++t;}cnt[t] += 1;}for (int i = 0, s = 0; i < 20; ++i) {s += cnt[i];ans += std::min(s, n - s);}}std::cout << ans;
}
```C++