分解质因数-求完全平方数

题目来源

www.acwing.com/problem/content/3493/

题目

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

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

输入格式

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

输出格式

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

数据范围

对于 30% 的评测用例，$1≤n≤1000$，答案不超过 $1000$。

对于 60% 的评测用例，$1≤n≤10^8$，答案不超过 $10^8$。

对于所有评测用例，$1≤n≤10^{12}$，答案不超过 $10^{12}$。

输入样例1

输出样例1

输入样例2

输出样例2

AC代码

用到了分解质因数操作还是有必要记录以下，说一下题目思路。以样例分析，样例给的12求一个数乘以12是完全平方数，我们把12进行分解$32^2=12$ ，我们只需要补一个质因数3就可以变成完全平方数$3^22^2=36$了

#include <iostream>
using namespace std;
typedef long long LL;
int main(){
    LL n;
    cin>>n;
    LL res = 1;
    //分解质因数
    for(LL i = 2;i*i<=n;i++){
        int s = 0;
        while(n%i == 0){
            s++;
            n/=i;
        }
        if(s%2) res*=i;
    }
    if(n>1) res*=n;
    cout<<res<<endl;
    return 0;
}