[蓝桥杯 2021 省 AB2] 完全平方数

题目链接

[蓝桥杯 2021 省 AB2] 完全平方数

题目描述

一个整数 $a$ 是一个完全平方数，是指它是某一个整数的平方，即存在一个 整数 $b$，使得 $a=b^2$。

给定一个正整数 $n$，请找到最小的正整数 $x$，使得它们的乘积是一个完全平方数。

输入格式

输入一行包含一个正整数 $n$。

输出格式

输出找到的最小的正整数 $x$。

输入输出样例

输入

12

输出

3

输入

15

输出

15

数据范围

• $1\le n\le 10^{12}$

解法：数学 + 质因数分解

如果一个数 $a$ 是完全平方数，那么他一定有两个相同的因子 $b_1$ 和 $b_2$，使得 $b_1\times b_2=a$。

因为 $b_1$ 和 $b_2$ 是相等的，所以他们各自的质因数也相等。

我们就可以很容易的得出一个结论，如果一个数 $a$ 是 完全平方数，那么 $a$ 的质因数个数一定是偶数个！

举例，$a=36$ 是一个完全平方数，将其质因数分解为 $a=36=2\times 2\times 3\times 3$。

示例一，$n=12=2\times 2\times 3$，我们发现 $3$ 这个因子只有一个是 奇数个 ，所以我们要将其变为 偶数个 才能使得 $n$ 变成完全平方数，我们只要让 $n$ 乘上一个 $3$ 即可。

所以我们可以直接对 $n$ 进行 质因数分解，对于奇数个的质因子，我们都要补充一个，我们最终的答案就是所有这些需要补充的质因子的乘积！

时间复杂度：$O(\sqrt{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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

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);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39