题目描述：
对于一个序列，牛牛每次可以将序列中任意一个位置上的数乘上任意一个质数。
现在他想知道至少需要多少次操作才能使得该序列中的任意两个不同位置的数相乘都为完全平方数。
完全平方数：对于x，若其可以写成
i
×
i
=
x
i×i=x
i×i=x的形式，则称x为完全平方数。
提示：一个数是完全平方数的充要条件是其所有质因子的指数都为偶数，例如
2
2
×
3
2
=
36
2^2 × 3^2 =36
22×32=36
输入描述：
第一行输入一个整数N，表示序列长度
接下来一行输入N个整数，表示该序列
对于
100
%
的数据，
1
≤
N
≤
1
0
5
，
1
≤
序列中的数
≤
1
0
5
对于100\% 的数据，1 ≤ N ≤ 10^5 ， 1 ≤ 序列中的数 ≤ 10^5
对于100%的数据，1≤N≤105，1≤序列中的数≤105
输出描述：
输出一个整数表示答案
示例1：
输入
3
2 1 2
输出
1
说明
只需要将第二个1乘上2即可，这样序列就变为2 2 2，任意两个数相乘都是4
示例2：
输入
3
2 4 6
输出
2
说明
将4乘上2，将6乘上3，序列变为2 8 18，任意两个数相乘都是完全平方数
#include <bits/stdc++.h>
using namespace std;
map<int, int> odd,even;
//记录在给出的n个数中，针对各个质因数的指数为偶数或者奇数的个数
//比如odd[2]=1就代表在n个数中质因数2的指数为奇数的有1个
void divide(int n)
{
for(int i=2;i*i<=n;i++)
if(n%i==0)
{
int s=0;
while(n%i==0)
{
n/=i;
s++;
}
if(s%2==1){
odd[i]++;
}
else{
even[i]++;
}
}
if(n>1) odd[n]++;//到最后若n>1,代表还有一个大于根号n的质因数存在
}
//注意：比如9不存在质因数2，那么相当于其质因数2的指数为0，相当于应该even[2]加上1。但我们的记录并没有记录这种情况的。所以odd[i]+even[i]可能小于n
int main()
{
int n, x,maxx=0, res=0;
cin >> n;
for(int i = 0; i < n; i ++)
{
cin >> x;
maxx=max(x,maxx);
divide(x);
}
for(int i = 2; i<maxx+1; i++)//最大的质因数不可能超过maxx,i可直接从2开始
{
//质因数i的指数均为偶数时不用做任何操作
//质因数i的指数均为奇数时要考虑有比如不存在该质因数的数的存在，比如9不存在质因数2，即指数为0。
if(odd[i] != 0 && odd[i] < n)//如果odd[i]==n的话说明输入的n个数中不会有 上述这种数的存在 自然也就不用操作了
res += min(odd[i], n - odd[i]);//n-odd[i]就是把 上述这种数的存在 考虑了进来。如果写成min(odd[i], even[i])就错了
//上面这行代码意思就是要么把奇数都转化为偶数，或 上述这种数 都转化为奇数(两种情况取小)
}
cout << res << endl;
return 0;
}
可以用输入
4
1 2 4 6
代入理解上述代码
