[藍(lán)橋杯 2021 省 AB2] 完全平方數(shù)

題目描述

一個(gè)整數(shù) $a$ 是一個(gè)完全平方數(shù)，是指它是某一個(gè)整數(shù)的平方，即存在一個(gè) 整數(shù) $b$，使得 $a=b^2$ 。

給定一個(gè)正整數(shù) $n$，請(qǐng)找到最小的正整數(shù) $x$，使得它們的乘積是一個(gè)完全平方數(shù)。

輸入格式

輸入一行包含一個(gè)正整數(shù) $n$。

輸出格式

輸出找到的最小的正整數(shù) $x$。

樣例 #1

樣例輸入 #1

12

樣例輸出 #1

3

樣例 #2

樣例輸入 #2

15

樣例輸出 #2

15

提示

對(duì)于 $30\%$ 的評(píng)測(cè)用例, $1\le n\le 1000$，答案不超過(guò) $1000$。

對(duì)于 $60\%$ 的評(píng)測(cè)用例，$1\le n\le 10^8$，答案不超過(guò) $10^8$。

對(duì)于所有評(píng)測(cè)用例，$1\le n\le 10^{12}$，答案不超過(guò) $10^{12}$。

藍(lán)橋杯 2021 第二輪省賽 A 組 G 題（B 組 H 題）。

思路：

這一看直接暴力就只能得一點(diǎn)點(diǎn)分，我還數(shù)論學(xué)的不太好先暴力得了30分。然后開(kāi)始想辦法吧！
沒(méi)辦法。。。看答案吧。。。

理論補(bǔ)充：完全平方數(shù)的一個(gè)性質(zhì)：完全平方數(shù)的質(zhì)因子的指數(shù)一定為偶數(shù)

1.唯一分解定理任意一個(gè)數(shù) n，它都可以分解為若干個(gè)質(zhì)數(shù)的乘積。

2.需要知道完全平方數(shù)的一個(gè)性質(zhì)：完全平方數(shù)的質(zhì)因子的指數(shù)一定為偶數(shù)。附上大佬的證明過(guò)
程：

最終思路：

對(duì)n進(jìn)行質(zhì)因數(shù)分解，如果質(zhì)因數(shù)的指數(shù)為奇數(shù)的話就在x中乘以這個(gè)質(zhì)因子這樣，可以讓指數(shù)保持偶數(shù)，如果是偶數(shù)那就不用管它~~~~
1.分解質(zhì)因子：

for (long long i = 2; i * i <= n; i++){if (n % i == 0){cnt++;//記錄有多少個(gè)因子，后面好遍歷}while (n % i == 0){a[cnt] = i;//a數(shù)組存因子g[cnt]++;//g數(shù)組存因子指數(shù)n = n / i;}}if (n > 1){a[++cnt] = n;g[cnt]++;}//考慮沒(méi)分解完的情況

2,根據(jù)性質(zhì)得出答案：

  for (int i = 1; i <= cnt; i++)//遍歷如果有奇數(shù)就讓原來(lái)的n*ans*這個(gè)奇數(shù)質(zhì)因子也就是讓ans*這個(gè)奇數(shù)質(zhì)因子{if (g[i] % 2){ans = ans * a[i];}}cout << ans;

小插曲：

質(zhì)因數(shù)分解寫錯(cuò)了最后輸出了和n一樣的數(shù)竟然得了60分！！

全部代碼

#include <iostream>
using namespace std;long long n, ans = 1, g[1000], a[1000], cnt;
int main()
{cin >> n;// 首先對(duì)n進(jìn)行質(zhì)因數(shù)分解for (long long i = 2; i * i <= n; i++){if (n % i == 0){cnt++;//記錄有多少個(gè)因子，后面好遍歷}while (n % i == 0){a[cnt] = i;//a數(shù)組存因子g[cnt]++;//g數(shù)組存因子指數(shù)n = n / i;}}if (n > 1){a[++cnt] = n;g[cnt]++;}//考慮沒(méi)分解完的情況//完全平方數(shù)的質(zhì)因子的指數(shù)一定為偶數(shù)for (int i = 1; i <= cnt; i++)//遍歷如果有奇數(shù)就讓原來(lái)的n*ans*這個(gè)奇數(shù)質(zhì)因子也就是讓ans*這個(gè)奇數(shù)質(zhì)因子{if (g[i] % 2){ans = ans * a[i];}}cout << ans;system("pause");return 0;
}