题目链接
题目描述
一个整数 a a a 是一个完全平方数,是指它是某一个整数的平方,即存在一个 整数 b b b,使得 a = b 2 a = b^2 a=b2。
给定一个正整数 n n n,请找到最小的正整数 x x x,使得它们的乘积是一个完全平方数。
输入格式
输入一行包含一个正整数 n n n。
输出格式
输出找到的最小的正整数 x x x。
输入输出样例
输入
12
输出
3
输入
15
输出
15
数据范围
- 1 ≤ n ≤ 1 0 12 1 \leq n \leq 10^{12} 1≤n≤1012
解法:数学 + 质因数分解
如果一个数 a a a 是完全平方数,那么他一定有两个相同的因子 b 1 b_1 b1 和 b 2 b_2 b2,使得 b 1 × b 2 = a b_1 \times b_2 = a b1×b2=a。
因为 b 1 b_1 b1 和 b 2 b_2 b2 是相等的,所以他们各自的质因数也相等。
我们就可以很容易的得出一个结论,如果一个数 a a a 是 完全平方数,那么 a a a 的质因数个数一定是偶数个!
举例, a = 36 a = 36 a=36 是一个完全平方数,将其质因数分解为 a = 36 = 2 × 2 × 3 × 3 a = 36 = 2 \times 2 \times 3\times 3 a=36=2×2×3×3。
示例一, n = 12 = 2 × 2 × 3 n = 12 = 2 \times 2 \times 3 n=12=2×2×3,我们发现 3 3 3 这个因子只有一个是 奇数个 ,所以我们要将其变为 偶数个 才能使得 n n n 变成完全平方数,我们只要让 n n n 乘上一个 3 3 3 即可。
所以我们可以直接对 n n n 进行 质因数分解,对于奇数个的质因子,我们都要补充一个,我们最终的答案就是所有这些需要补充的质因子的乘积!
时间复杂度: O ( n ) O(\sqrt{n}) O(n)
C++代码:
#include <iostream>
#include <unordered_map>
#include <functional>
using namespace std;
using LL = long long;
unordered_map<LL, int> cnt;
void fun(LL x)
{
for(int i = 2;i <= x / i;i++){
while(x % i == 0){
cnt[i]++;
x /= i;
}
}
if(x > 1) cnt[x]++;
}
void solve(){
LL n;
cin>>n;
fun(n);
LL ans = 1;
for(auto [k, v]:cnt){
if(v & 1) ans *= k;
}
cout<<ans<<'\n';
}
int main(){
int t = 1;
while(t--)
{
solve();
}
return 0;
}
Java代码:
import java.util.*;
import java.io.*;
public class Main{
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static Map<Long, Integer> map;
public static void fun(long x)
{
map = new HashMap<>();
for(long i = 2;i <= x / i;i++)
{
while(x % i == 0)
{
map.put(i, map.getOrDefault(i, 0) + 1);
x /= i;
}
}
if(x > 1) map.put(x, map.getOrDefault(x, 0) + 1);
}
public static void main(String[] args) throws Exception
{
long n = Long.parseLong(in.readLine().trim());
fun(n);
long t = 1;
for(long k:map.keySet())
{
int cnt = map.get(k);
if((cnt & 1) == 1) t *= k;
//System.out.println(k + " " + cnt);
}
System.out.println(t);
}
}