[蓝桥杯 2021 省 AB2] 完全平方数
[蓝桥杯 2021 省 AB2] 完全平方数
题目描述
一个整数 a a a 是一个完全平方数，是指它是某一个整数的平方，即存在一个 整数 b b b，使得 a = b 2 a=b^{2} a=b2 。
给定一个正整数 n n n，请找到最小的正整数 x x x，使得它们的乘积是一个完全平方数。
输入格式
输入一行包含一个正整数 n n n。
输出格式
输出找到的最小的正整数 x x x。
样例 #1
样例输入 #1
12
样例输出 #1
3
样例 #2
样例输入 #2
15
样例输出 #2
15
提示
对于 30 % 30 \% 30% 的评测用例, 1 ≤ n ≤ 1000 1 \leq n \leq 1000 1≤n≤1000，答案不超过 1000 1000 1000。
对于 60 % 60 \% 60% 的评测用例， 1 ≤ n ≤ 1 0 8 1 \leq n \leq 10^{8} 1≤n≤108，答案不超过 1 0 8 10^{8} 108。
对于所有评测用例， 1 ≤ n ≤ 1 0 12 1 \leq n \leq 10^{12} 1≤n≤1012，答案不超过 1 0 12 10^{12} 1012。
蓝桥杯 2021 第二轮省赛 A 组 G 题（B 组 H 题）。
知识点一：
唯一分解定理
唯一分解
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
int ans=1;
signed main() {
cin>>n;
for(int i=2;i*i<=n;i++) //找到质因子
{
int cnt=0;
while(n%i==0)//如果n=12 i=2 两轮过去 12-6-3 所以i=4没有 在i=2的时候已经处理了
{
cnt++;
n/=i;
}
if(cnt%2!=0) ans*=i; //当i=3 cnt=1 ans*=3
}
ans*=n;//如果还有别的因子
cout<<ans;
return 0;
}
原文地址：https://blog.csdn.net/kazuma_hn/article/details/137450057
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！