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

题目描述

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

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

12

样例输出 #1

3

样例 #2

样例输入 #2

15

样例输出 #2

15

提示

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

对于 $60\%$ 的评测用例，1≤n≤1081 \\leq n \\leq 10^{8}1≤n≤108，答案不超过 10810^{8}108。

对于所有评测用例，1≤n≤10121 \\leq n \\leq 10^{12}1≤n≤1012，答案不超过 101210^{12}1012。

蓝桥杯 2021 第二轮省赛 A 组 G 题（B 组 H 题）。

思路：

这一看直接暴力就只能得一点点分，我还数论学的不太好先暴力得了30分。然后开始想办法吧！
没办法。。。看答案吧。。。

理论补充：完全平方数的一个性质：完全平方数的质因子的指数一定为偶数

1.唯一分解定理任意一个数 n，它都可以分解为若干个质数的乘积。

2.需要知道完全平方数的一个性质：完全平方数的质因子的指数一定为偶数。附上大佬的证明过
程：

最终思路：

对n进行质因数分解，如果质因数的指数为奇数的话就在x中乘以这个质因子这样，可以让指数保持偶数，如果是偶数那就不用管它~~~~
1.分解质因子：

for (long long i = 2; i * i <= n; i++){if (n % i == 0){cnt++;//记录有多少个因子，后面好遍历}while (n % i == 0){a[cnt] = i;//a数组存因子g[cnt]++;//g数组存因子指数n = n / i;}}if (n > 1){a[++cnt] = n;g[cnt]++;}//考虑没分解完的情况

2,根据性质得出答案：

  for (int i = 1; i <= cnt; i++)//遍历如果有奇数就让原来的n*ans*这个奇数质因子也就是让ans*这个奇数质因子{if (g[i] % 2){ans = ans * a[i];}}cout << ans;

小插曲：

质因数分解写错了最后输出了和n一样的数竟然得了60分！！

全部代码

#include <iostream>
using namespace std;long long n, ans = 1, g[1000], a[1000], cnt;
int main()
{cin >> n;// 首先对n进行质因数分解for (long long i = 2; i * i <= n; i++){if (n % i == 0){cnt++;//记录有多少个因子，后面好遍历}while (n % i == 0){a[cnt] = i;//a数组存因子g[cnt]++;//g数组存因子指数n = n / i;}}if (n > 1){a[++cnt] = n;g[cnt]++;}//考虑没分解完的情况//完全平方数的质因子的指数一定为偶数for (int i = 1; i <= cnt; i++)//遍历如果有奇数就让原来的n*ans*这个奇数质因子也就是让ans*这个奇数质因子{if (g[i] % 2){ans = ans * a[i];}}cout << ans;system("pause");return 0;
}