3491. 完全平方数 - AcWing题库

题目描述

分析 

完全平方数的一个特点：

所有的质因子的个数为偶数。eg1.9的质因子为3，3的个数为2，得到了9（3*3=9）

                                               eg2.81的质因子为3，3的个数为4，得到81（3*3*3*3=81）

我们将答案乘以不是偶数的质因子，也就是将这个质因子的个数加一变成了偶数，最后这些质因子全部变成偶数，这样它就是一个完全平方数

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
unordered_map<ll, ll> primes;
ll n;
int main()
{cin >> n;for(int i = 2; i <= n / i; i ++){while(n % i == 0){n /= i;primes[i] ++;}}if(n > 1)primes[n] ++;ll ans = 1;for(auto i : primes){if(i.second % 2 != 0)ans *= i.first;}cout << ans;return 0;
}