[数据结构与算法]AcWing 3491. 完全平方数 (分解质因数)

来源：第十二届蓝桥杯省赛第二场C++A/B组

AcWing 3491. 完全平方数

一个整数?aa?是一个完全平方数，是指它是某一个整数的平方，即存在一个整数?bb，使得?a=b2a=b2。

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

输入格式

输入一行包含一个正整数?nn。

输出格式

输出找到的最小的正整数?xx。

数据范围

对于?30%30%?的评测用例，1≤n≤10001≤n≤1000，答案不超过?10001000。
对于?60%60%?的评测用例，1≤n≤1081≤n≤108，答案不超过?108108。
对于所有评测用例，1≤n≤10121≤n≤1012，答案不超过?10121012。

输入样例1：

12

输出样例1：

3

输入样例2：

15

输出样例2：

15

AC

#include<stdio.h>
#include<iostream>
using namespace std;
typedef long long ll;
int main(void)
{
	ll n;
	cin>>n;
	for(ll i=2;i*i<=n;i++)//剔除所有的偶数次的质因子 
	{
		while(n%(i*i)==0)
		{
			n/=i*i;
		}	
	}
	cout<<n<<endl; 
	return 0;
}