完全平方数

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

题目描述

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

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

12

样例输出 #1

3

样例 #2

样例输入 #2

15

样例输出 #2

15

提示

对于30%的评测用例, 1<=n<=1000，答案不超过 1000。

对于 60%的评测用例，1<=n<=1e8，答案不超过 1e8。

对于所有评测用例，1<=n<=1e12，答案不超过 1e12。

理解

代码

30分代码

#include <iostream>
#include<cstdio>
#include <sstream>
#include<algorithm>
#include<cmath>
#include<string>
#include<set>

using namespace std;

int main()
{

   long long  n;
   cin>>n;
   for(int i=1;;i++)
   {
       int s=sqrt(n*i);
       if(s*s==n*i)
       {
           cout<<i;
           break;
       }
   }
    return 0;
}

满分代码

#include <iostream>
#include<cstdio>
#include <sstream>
#include<algorithm>
#include<cmath>
#include<string>
#include<set>

using namespace std;

long long n,ans=1;
int main()
{
    scanf("%lld",&n);
    for(long long i=2;i*i<=n;i++)
        {
        	int cnt=0; //cnt计数，表示质因子pri[i]的指数
        	while(!(n%i))cnt++,n/=i;
        	if(cnt%2)ans*=i; //如果指数不是偶数，在x中要有一个这个质因子，保证指数为偶数
		}
	if(n!=1)ans*=n;//注意n没分尽的情况
	printf("%lld",ans);
	return 0;
}