题目描述
一个整数 a 是一个完全平方数,是指它是某一个整数的平方,即存在一个整数 b,使得 a=b2。
给定一个正整数 n,请找到最小的正整数 x,使得它们的乘积是一个完全平方数。
输入格式
输入一行包含一个正整数 n。
输出格式
输出找到的最小的正整数 x。
数据范围
对于 30% 的评测用例,1≤n≤1000,答案不超过 1000。
对于 60% 的评测用例,1≤n≤108,答案不超过 108。
对于所有评测用例,1≤n≤1012,答案不超过 1012。
样例
输入样例1:
12
输出样例1:
3
输入样例2:
15
输出样例2:
15
算法1
(分解质因数) $O(n)$
将n分解质因数, 判断每个质因数的个数,如果质因数的个数是奇数个,则答案乘以这个质因数。
时间复杂度
$O(n)$
参考文献
算法基础课
C++ 代码
#include <iostream>
#include <map>
#define x first
#define y second
using namespace std;
typedef long long LL;
map<LL, LL> primes;
LL n;
int main()
{
cin >> n;
for (LL i = 2; i <= n / i; i++)
{
while (n % i == 0)
{
primes[i]++;
n /= i;
}
}
if (n > 1) primes[n]++;
LL res = 1;
for (auto p : primes)
{
if (p.y & 1) res = res * p.x;
}
cout << res << endl;
return 0;
}