第十二届蓝桥杯省赛第二场 C++ B组 - 完全平方数

问题描述

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

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

输入格式

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

输出格式

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

数据范围

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

对于 60% 的评测用例，1≤n≤10⁸，答案不超过 10⁸。

对于所有评测用例，1≤n≤10¹²。

输入样例1：

12
• 1

输出样例1：

3

输入样例2：

15
• 1

输出样例2：

15

思路

这道题想要拿满分必然不能使用暴力来做，我们可以通过完全平方数的性质来看。完全平方数可以拆分成质因子的偶数次方相乘，比如 36 = 22 * 32 ，49 = 72 等。

如果给出一个不是完全平方数的 n ，那么它肯定能拆分出一个次数为奇数的质因子，那么我们再将 n 乘上这个次数为奇数的质因子，n 中所有质因子的次数就都是偶数了即成为完全平方数，比如 12 = 22 * 3 ，故 12 * 3 = 22 * 32 = 36 。

所以我们只用除去所有次数为偶数的质因子就可以得到次数为奇数的质因子了，即题目所求。

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
  long long n;
  cin >> n;
  for (long long i = 2; i * i <= n; i++) {
    while (n % (i * i) == 0)
      n /= i * i;
  }
  cout << n << endl;
  return 0;
}