完全平方数(分解质因数)

题目链接:https://www.acwing.com/problem/content/3494/

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

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

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

第二行包含 n n n 个整数 A 1 , A 2 , ⋅ ⋅ ⋅ , A n A_1,A_2,⋅⋅⋅,A_n A1​,A2​,⋅⋅⋅,An​。

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

数据范围
对于 30% 的评测用例， 1 ≤ n ≤ 1000 1≤n≤1000 1≤n≤1000，答案不超过 1000 1000 1000。
对于 60% 的评测用例， 1 ≤ n ≤ 1 0 8 1≤n≤10^8 1≤n≤108，答案不超过 1 0 8 10^8 108。
对于所有评测用例， 1 ≤ n ≤ 1 0 12 1≤n≤10^{12} 1≤n≤1012，答案不超过 1 0 12 10^{12} 1012。

输入样例1：

12

输出样例1：

3

输入样例2：

15

输出样例2：

15

因为每个完全平方数分解质因数后，每个质因数的指数都是偶数
所以只要把n分解质因数，再乘以指数是奇数的质因数就是答案

AC代码

#include 

using namespace std;

typedef long long LL;

LL n,ans = 1;

int main()
{
    cin >> n;
    for(LL i = 2; i * i <= n; i++)
    {
        int cnt = 0;
        while(n % i == 0)
        {
            n /= i;
            cnt++;
        }
        if(cnt != 0 && cnt % 2 != 0) ans *= i;
    }
    if(n > 1) ans *= n;
    cout << ans << endl;
    return 0;
}