题解 | #小苯的数字权值#
小苯的数字权值
http://www.nowcoder.com/questionTerminal/aeacca655eec45999a6dc4d998dfd4a5
这个问题涉及到数字的权值计算，其中权值定义为数字的正因子个数。我们需要比较将数字拆分成质因数与不拆分时的权值和。
### 情况1：质因数只有一种
以 \(8 = 2^3\) 为例：
- **不拆分**：8 的因子有 1, 2, 4, 8，共 4 个，所以权值和为 4。
- **拆分**：将 8 拆分成 3 个 2，每个 2 的权值为 2，所以权值和为 \(3 \times 2 = 6\)。
### 情况2：质因数有多种
以 \(70 = 2 \times 5 \times 7\) 为例：
- **不拆分**：70 的因子有 1, 2, 5, 7, 10, 14, 35, 70，共 8 个，所以权值和为 8。
- **拆分**：将 70 拆分成 3 个质因数 2, 5, 7，每个质因数的权值为 2，所以权值和为 \(3 \times 2 = 6\)。
### 一般情况
对于一个数 \(n\)，假设其质因数分解为：
\[ n = p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_k^{e_k} \]
- **不拆分**：\(n\) 的因子数量为 \((e_1 + 1)(e_2 + 1) \cdots (e_k + 1)\)。
- **拆分**：将 \(n\) 拆分成 \(e_1 + e_2 + \cdots + e_k\) 个质因数，每个质因数的权值为 2，所以权值和为 \(2(e_1 + e_2 + \cdots + e_k)\)。
### 比较
- 当 \(k = 1\)（即只有一个质因数）时，不拆分的权值和为 \(e_1 + 1\)，拆分的权值和为 \(2e_1\)。显然，当 \(e_1 > 1\) 时，拆分的权值和更大。
- 当 \(k > 1\)（即有多个质因数）时，不拆分的权值和为 \((e_1 + 1)(e_2 + 1) \cdots (e_k + 1)\)，拆分的权值和为 \(2(e_1 + e_2 + \cdots + e_k)\)。通常情况下，不拆分的权值和更大。
### 结论
- 对于只有一个质因数且指数大于 1 的数，拆分后权值和更大。
- 对于有多个质因数的数，不拆分的权值和通常更大。
因此，对于给定的问题，我们需要根据具体情况选择是否拆分。在质因数只有一种且指数大于 1 时，拆分是更好的选择。在有多个质因数时，不拆分通常更优。
### 情况1：质因数只有一种
以 \(8 = 2^3\) 为例：
- **不拆分**：8 的因子有 1, 2, 4, 8，共 4 个，所以权值和为 4。
- **拆分**：将 8 拆分成 3 个 2，每个 2 的权值为 2，所以权值和为 \(3 \times 2 = 6\)。
### 情况2：质因数有多种
以 \(70 = 2 \times 5 \times 7\) 为例：
- **不拆分**：70 的因子有 1, 2, 5, 7, 10, 14, 35, 70，共 8 个，所以权值和为 8。
- **拆分**：将 70 拆分成 3 个质因数 2, 5, 7，每个质因数的权值为 2，所以权值和为 \(3 \times 2 = 6\)。
### 一般情况
对于一个数 \(n\)，假设其质因数分解为：
\[ n = p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_k^{e_k} \]
- **不拆分**：\(n\) 的因子数量为 \((e_1 + 1)(e_2 + 1) \cdots (e_k + 1)\)。
- **拆分**：将 \(n\) 拆分成 \(e_1 + e_2 + \cdots + e_k\) 个质因数，每个质因数的权值为 2，所以权值和为 \(2(e_1 + e_2 + \cdots + e_k)\)。
### 比较
- 当 \(k = 1\)（即只有一个质因数）时，不拆分的权值和为 \(e_1 + 1\)，拆分的权值和为 \(2e_1\)。显然，当 \(e_1 > 1\) 时，拆分的权值和更大。
- 当 \(k > 1\)（即有多个质因数）时，不拆分的权值和为 \((e_1 + 1)(e_2 + 1) \cdots (e_k + 1)\)，拆分的权值和为 \(2(e_1 + e_2 + \cdots + e_k)\)。通常情况下，不拆分的权值和更大。
### 结论
- 对于只有一个质因数且指数大于 1 的数，拆分后权值和更大。
- 对于有多个质因数的数，不拆分的权值和通常更大。
因此，对于给定的问题，我们需要根据具体情况选择是否拆分。在质因数只有一种且指数大于 1 时，拆分是更好的选择。在有多个质因数时，不拆分通常更优。
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt(); // 读取测试用例数量while (n-- > 0) {solve(scanner); // 处理每个测试用例}}public static void solve(Scanner scanner) {int x = scanner.nextInt(); // 读取当前测试用例的数字int sum = 1; // 初始化不拆分的权值和int splitSum = 0; // 初始化拆分的权值和// 遍历所有可能的质因数for (int i = 2; i * i <= x; i++) {if (x % i == 0) { // 如果 i 是 x 的质因数int cnt = 0; // 初始化当前质因数的指数while (x % i == 0) { // 计算质因数 i 的指数x /= i;cnt++;}sum *= (cnt + 1); // 更新不拆分的权值和splitSum += 2 * cnt; // 更新拆分的权值和}}// 处理剩余的质数 如果 x > 1，说明 x 是一个质数if (x > 1) {sum *= 2; // 更新不拆分的权值和splitSum += 2; // 更新拆分的权值和}System.out.println(Math.max(splitSum, sum)); // 输出最大权值和}}
