自己做网站排版,广西南宁网站空间,户外拓展网站源码,网站续费服务商问题描述
蓝桥村是蓝桥王国年年的模范村#xff0c;这是因为他们村的稻田每年都是优美的。
对于一块稻田来说#xff0c;如果其中任意两根不同的秧苗的高度乘积均为完全平方数#xff0c;该稻田被称之为优美的稻田。
蓝桥王国的稻田验收日即将到来#xff0c;但现在蓝桥…问题描述
蓝桥村是蓝桥王国年年的模范村这是因为他们村的稻田每年都是优美的。
对于一块稻田来说如果其中任意两根不同的秧苗的高度乘积均为完全平方数该稻田被称之为优美的稻田。
蓝桥王国的稻田验收日即将到来但现在蓝桥村还有一块插了 根秧苗的稻田不够优美其中第 根秧苗的高度为 ℎ。
作为蓝桥杯的村长你可以发动技能拔苗助长
选择一个质数 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 ArrayListInteger primeList;public static void main(String[] args) {e_sieve();System.out.println(primeList);Scanner sc new Scanner(System.in);int n sc.nextInt();MapInteger, Integer mapAll new HashMapInteger, Integer();for (int i 0; i n; i) {int temp sc.nextInt();MapInteger, Integer map new HashMapInteger, 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.EntryInteger, 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 ArrayListInteger();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;}}}}
}
