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

题目描述

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

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

提示

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

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

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

蓝桥杯 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;
}