当前位置：首页 > news >正文

蓝桥杯完全平方数刷题笔记

news 来源：原创 2025/8/28 18:12:43

关键分析

---

### **完全平方数的质因数指数特性**
**核心结论**：
一个数是完全平方数，当且仅当它的所有质因数的指数均为偶数。

---

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;signed main(){cin >> n;int res = 1;for(int i = 2; i*i <= n; i++){  // 枚举质因子，从小的开始if(n % i == 0){int s = 0;while(n % i == 0) s++, n /= i;  // 计算质因子i的次数sif(s % 2) res *= i;  // 如果次数是奇数，乘到结果中}}if(n > 1) res *= n;  // 处理剩余的大质因子cout << res << endl;return 0;
}

### **n = 199994535 的质因数分解过程**

---

#### **步骤1：初始化**
- **目标**：将 `n = 199994535` 分解为质因数的乘积形式。
- **初始值**：`n = 199994535`

---

#### **步骤2：试除小质数**
1. **判断是否能被2整除**：
- `199994535` 是奇数，无法被2整除。

2. **判断是否能被5整除**：
- **末位是5**，可以直接整除。
- **计算**：`199994535 ÷ 5 = 39998907`。
- **记录质因数**：`5^1`。
- **更新n**：`n = 39998907`。

3. **继续判断是否能被5整除**：
- `39998907` 末位是7，无法被5整除。

4. **判断是否能被3整除**：
- **各位和**：`3+9+9+9+8+9+0+7 = 54`，能被3整除。
- **计算**：`39998907 ÷ 3 = 13332969`，次数 `s=1`。
- **继续除以3**：`13332969 ÷ 3 = 4444323`，次数 `s=2`。
- **继续除以3**：`4444323 ÷ 3 = 1481441`，次数 `s=3`。
- **继续除以3**：`1481441 ÷ 3 = 493813.666...`（无法整除）。
- **记录质因数**：`3^3`。
- **更新n**：`n = 1481441`。

---

#### **步骤3：处理剩余的大质数**
- **当前n**：`1481441`。
- **试除到平方根**：`√1481441 ≈ 1217`。
- **尝试质数3到1217**：
- **3**：已处理过。
- **5**：末位非0/5。
- **7**：`1481441 ÷ 7 ≈ 211634.428`（余数非0）。
- **11**：交替和法验证，无法整除。
- **13**：`1481441 ÷ 13 ≈ 113957`（余数非0）。
- ...（继续试除所有质数到1217）。
- **结论**：未找到其他质因数。
- **记录质因数**：`1481441^1`。

---

#### **最终质因数分解**
$$
199994535 = 5^1 \times 3^3 \times 1481441^1
$$

---

#### **步骤4：计算最小x**
- **目标**：使所有质因数的指数为偶数。
- **分析**：
- `5` 的指数为 `1`（奇数），需乘一次 `5`。
- `3` 的指数为 `3`（奇数），需乘一次 `3`。
- `1481441` 的指数为 `1`（奇数），需乘一次 `1481441`。
- **结果**：

x = 5 *3 * 1481441 = 22221615

---

### **最终答案**
- **最小x**：`22221615`
- **验证**：`199994535 × 22221615` 是完全平方数。

相关文章：