3491. 完全平方数 题解

跳转链接 ​

https://www.acwing.com/problem/content/3494/ 来源：第十二届蓝桥杯省赛第二场C++A/B组

题目描述 ​

一个整数 a 是一个完全平方数，是指它是某一个整数的平方，即存在一个整数 b，使得 a=b2。 给定一个正整数 n，请找到最小的正整数 x，使得它们的乘积是一个完全平方数。

输入格式 输入一行包含一个正整数 n。 输出格式 输出找到的最小的正整数 x。 每个 id 占一行。 数据范围 对于 30% 的评测用例，1≤n≤1000，答案不超过 1000。 对于 60% 的评测用例，1≤n≤10^8^，答案不超过 10^8^。 对于所有评测用例，1≤n≤10^12^，答案不超过 10^12^。 输入样例1 12 输出样例1 3

输入样例1 15 输出样例1 15

题解思路 ​

假设一个数是完全平方数,那么它的每个质因数一定是偶数个 如100可以分解为2^2^ * 5^2^,其中2出现了2次，5出现了2次

换一种思想，假设完全平方数表示为m,它的平方根为n，那么n * n = m; 由于n可以分解为x个质因子，有2个n构成m 所以必然是由2x个质因子构成一个完全平方数,完全平方数的质因数必然是成对出现的

所以我们只需要对题目中给出的数据分解质因数,所有只出现奇数次的质因数相乘的结果就是答案

代码 ​

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

int main()
{
    LL n, res = 1;
    cin >> n;
    
    for(LL i = 2; i * i <= n; i++)
        if(n % i == 0)
        {
            int s = 0;
            while(n % i == 0) s++, n /= i;
            if(s % 2)   res *= i;
        }
        
    if(n > 1) res *= n;
    
    cout << res;
    return 0;
}