Problem J37: Absolute Value Brute Force / 暴力枚举之绝对值

版权信息： · 原题出自 HDU 5778

---

任务总览

任务名称	时间限制	内存限制	分数
暴力枚举之绝对值	1 sec	1024 MB	15 points

---

题目描述

给定一个正整数 $x$，请你找出一个正整数 $y$，使得满足以下两个条件：

1. $y \geq 2$；
2. $| y - x |$ 的绝对值最小；
3. $y$ 的质因数分解中，​ 每个质因数都恰好出现两次 ​（即 $y = p_1 ^ 2 \cdot p_2 ^ 2 \cdot \dots \cdot p_k ^ 2$，是某些质数的平方积）；

请你输出满足条件的 $| y - x |$ 的最小值。

---

输入格式

第一行是一个整数 $T$，表示测试数据组数（$1 \leq T \leq 50$）。

接下来 $T$ 行，每行一个整数 $x$（$1 \leq x \leq 10 ^ {18}$）。

---

输出格式

输出 $T$ 行，每行一个整数，表示每组数据的最小绝对差 $| y - x |$。

---

输入输出样例

输入示例

5
1112
4290
8716
9957
9095

输出示例

23
65
67
244
70

---

题目分析与解法

✅ 条件重述：

我们希望找到一个 $y$ 满足：

• 它是 ​ 多个质数平方的乘积 ​（例如 $y = 2 ^ 2 \cdot 3 ^ 2 = 36$）；
• 与输入数 $x$ 的距离 $| y - x |$ 最小。

✅ 特征总结：

• 满足要求的 $y$ 形如：
• 
• 也可以写为：

$y = (p_1 \cdot p_2 \cdot \dots\cdot p_k) ^ 2$即 $y$ 是一个​ 完全平方数 ​，且其平方根是由若干 不重复质数的乘积 组成。

---

✅ 解法思路：

1. 构造所有不重复质数乘积 $P$，其中 $P \leq 10 ^ 9$；
2. 枚举这些质数集合，计算 $y = P ^ 2$；
3. 对每个输入 $x$，找出最接近它的合法 $y$，返回 $| y - x |$ 最小值。

---

时间复杂度分析

步骤	复杂度
枚举质数组合 ($<10000$)	$O(2^k)$，$k≈15$
每组 $x$ 二分最优 $y$	$O(\log N)$
总复杂度	非常高效，支持 $T=50$

---