蓝桥杯第18489题——拔苗助长（质数+map）
问题描述
蓝桥村是蓝桥王国年年的模范村，这是因为他们村的稻田每年都是优美的。
对于一块稻田来说，如果其中任意两根不同的秧苗的高度乘积均为完全平方数，该稻田被称之为优美的稻田。
蓝桥王国的稻田验收日即将到来，但现在蓝桥村还有一块插了 𝑁 根秧苗的稻田不够优美，其中第 𝑖 根秧苗的高度为 ℎ𝑖。
作为蓝桥杯的村长，你可以发动技能拔苗助长：
- 选择一个质数 x (2 ≤ x ≤ 10^6) ，同时将任意一株高度为 ℎ 的秧苗变为 ℎ×𝑥。
请问你最少需要发动多少次拔苗助长才可以将该稻田变得优美。
输入格式
第一行输入一个整数 𝑁 (1 ≤ 𝑁 ≤ 10^5) 表示稻田中秧苗的数量。
第二行输入 𝑁N 个整数 ℎ1,ℎ2,ℎ3,⋯,ℎ𝑁 (1 ≤ 𝐴𝑖 ≤ 10^6) 表示秧苗的高度。
输出格式
输出一个整数表示答案。
输入样例
5
1 2 3 4 5
输出样例
3解题思路
题目说让每两个数相乘都是一个完全平方数，这里不难想到分解质因数，如果要满足这个要求，则需要任意两个数相乘，其所有质因数都是偶数个数。
对于任意质因数p，任意两个数相乘的结果中p的个数为偶数，则说明两个数中的p的个数要么都是奇数，要么都是偶数；反过来说，如果存在任意两个数a和b，假设a的质因数2的个数为1个，那么b的质因数2的个数如果是偶数，则a和b相乘的结果必不可能是完全平方数。
因此我们考虑对于每一个数x进行统计，计算其所有质因数出现的次数，对于某个质因数p，如果其对于某个x出现的次数为奇数，就记录一次；这样的目的是方便我们最终考虑是将每个数中的p都变成奇数个还是偶数个。
举一个具象化的例子，对于一个数列2 2 2 3：对质因数2来说，有三个x存在奇数个2；对质因数3来说，有一个x存在奇数个3。上述情况中，我们应该选择将所有x中质因数2的个数补齐到奇数个，这样只需要操作4 - 3 = 1次；而对于质因数3，我们应该选择补齐到偶数个，这样只需要操作1次。
所以可以考虑到，对于每个质因数p，其在每个x中出现奇数次的次数num，对答案的贡献是min(num, n - num)。
为了记录每一个x的每一个质因数的个数，我们可以使用Map数据结构，同时可以使用埃氏筛加快这个过程，我们筛选出log(N)以内所有质数逐一测试，如果在试除计算的最后没有变成1，则其本身就是一个质数，即自己的一个质因数。
import java.util.*;public class Main {static final int inf = (int) 1e9;static final int N = (int) Math.sqrt(1e6 + 1);static boolean[] prime;static ArrayList<Integer> primeList;public static void main(String[] args) {e_sieve();System.out.println(primeList);Scanner sc = new Scanner(System.in);int n = sc.nextInt();Map<Integer, Integer> mapAll = new HashMap<Integer, Integer>();for (int i = 0; i < n; i++) {int temp = sc.nextInt();Map<Integer, Integer> map = new HashMap<Integer, Integer>();for (int e : primeList) {while (temp % e == 0) {temp /= e;map.put(e, map.getOrDefault(e, 0) + 1);}if (temp == 1) {break;}}if (temp != 1) {map.put(temp, 1);}for (java.util.Map.Entry<Integer, Integer> e : map.entrySet()) {if (e.getValue() % 2 == 1) {mapAll.put(e.getKey(), mapAll.getOrDefault(e.getKey(), 0) + 1);}}}System.out.println(mapAll);long ans = 0;for (int e : mapAll.values()) {ans += Math.min(e, n - e);}System.out.print(ans);}static void e_sieve() {primeList = new ArrayList<Integer>();prime = new boolean[N];Arrays.fill(prime, true);prime[0] = false; prime[1] = false;for (int i = 2; i < N; i++) {if (prime[i]) {primeList.add(i);for (long j = 1L * i * i; j < N; j += i) {prime[(int)j] = false;}}}}
}