完全平方数——唯一分解定理

一、唯一分解定理是什么？

1.定义

唯一分解定理是数论中的一个重要定理，它告诉我们：

任何大于 1 的正整数，都可以唯一分解为若干个质数的乘积（忽略排列顺序）。

数学表达式：
对于任意正整数 $(n>1)$，可以表示为：
$n=p_1^{e_1}\times p_2^{e_2}\times \cdots \times p_k^{e_k}$
其中：

• $(p_1,p_2,\dots ,p_k)$ 是质数；
• $(e_1,e_2,\dots ,e_k)$ 是正整数；

---

2.示例

1. 12 的分解：
   $12=2^2\times 3^1$
   质因数是 $2$ 和 $3$。

2. 100 的分解：
   $100=2^2\times 5^2$
   质因数是 $2$ 和 $5$。
   修改后的格式如下：

3. 97 的分解：
   $97=97^1$
   $97$ 是质数，本身就是唯一分解。

---

3.代码模板

import java.util.*;
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n=sc.nextInt();//Math.sqrt(n)可以进行时间优化for(int i=2;i<=Math.sqrt(n);i++){if(n%i==0){int count=0;//记录当前质数i的幂次while(n%i==0){count++;n/=i;//除掉所有因子i}System.out.println(i+" "+count);//输出对应的因子 以及 它的幂次}}if(n>1){//如果没有除完，最后一个数一定是质因子System.out.println(n+" "+1);//输出对应的因子 以及 它的幂次}}
}

---

二、例题

1>问题描述（2021蓝桥杯省赛）

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

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

---

输入格式

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

---

输出格式

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

---

样例输入 1

12

样例输出 1

3

---

样例输入 2

15

样例输出 2

15

---

评测用例规模与约定

• 对于 30 的评测用例，$1\le n\le 1000$，答案不超过 $1000$。
• 对于 60 的评测用例，$1\le n\le 10^8$，答案不超过 $10^8$。
• 对于所有评测用例，$1\le n\le 10^{12}$，答案不超过 $10^{12}$。

---

2>解题思路

根据题意分析，我们要求最小的 $x$ 使得 $x\times n$ 是一个完全平方数。 显而易见的是，最坏情况，$x$ 只能是$n$本身。因此我们只需要在整数 $n$ 以内去寻找最小的 $x$ 即可。 结合唯一分解定理，任何一个大于1的整数，一定可以分解成一个或者多个质数（也叫素数）相乘。如果一个数是完全平方数，则经过唯一分解后，其质因子的幂次一定是偶数！ 例如：

1. $36$ 的分解
   $36=2^2\times 3^2$
   幂次：$2,2$（都是偶数）
   因此，$36$ 是完全平方数。

2. $144$ 的分解
   $144=2^4\times 3^2$
   幂次：$4,2$（都是偶数）
   因此，$144$ 是完全平方数。

3. $81$ 的分解
   $81=3^4$
   幂次：$4$（是偶数）
   因此，$81$ 是完全平方数。

4. $100$ 的分解
   $100=2^2\times 5^2$
   幂次：$2,2$（都是偶数）
   因此，$100$ 是完全平方数。

5. $72$ 的分解（反例）
   $72=2^3\times 3^2$
   幂次：$3,2$（$3$ 不是偶数）
   因此，$72$ 不是完全平方数。

至此，解题思路就很明了啦。唯一分解给定的$n$ 寻找其质因子，如果质因子对应的幂次是奇数，则需要补齐对应的一个质因子，把它累乘到答案中即可。

---

3>假娃

import java.util.*;// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);//测试用例数据规模比较大，必须用longlong ans=1;long n=sc.nextLong();for(long i=2;i<=Math.sqrt(n);i++){if(n%i==0){long count=0;while(n%i==0){count++;n/=i;}if(count%2==1){ans*=i;}}}if(n>1)ans*=n;System.out.println(ans);}
}

---

3>C嘎嘎

#include <iostream>
#include <cmath> // 用于 sqrt 函数
using namespace std;int main() {long long ans = 1; // 用 long long 处理大数long long n;cin >> n; // 输入 nfor (long long i = 2; i <= sqrt(n); i++) {if (n % i == 0) { // 判断是否为因子long long count = 0;while (n % i == 0) { // 统计当前因子的幂次count++;n /= i;}if (count % 2 == 1) { // 如果幂次是奇数ans *= i;}}}if (n > 1) ans *= n; // 如果 n 还大于 1，则 n 本身是一个质数cout << ans << endl; // 输出结果return 0;
}

---