1 条题解
-
0
我们要找的是:k + n² = m²,其中m和n都是非负整数。 整理这个方程: m² - n² = k (m - n)(m + n) = k
核心思路:枚举k的所有因子对
对于k的每个因子对(d1, d2),满足d1 × d2 = k,我们可以得到:
m - n = d1 m + n = d2
解这个方程组:
m = (d1 + d2) / 2 n = (d2 - d1) / 2
重要条件:
d1和d2必须同奇偶(这样才能保证m和n是整数) m和n都必须是非负整数 m²就是我们要找的完全平方数
算法步骤:
如果k是0,直接输出0(因为0²=0) 枚举|k|的所有因子d(从1到√|k|) 对于每个因子d,考虑四种情况: (d1, d2) = (d, k/d) (d1, d2) = (-d, -k/d) (d1, d2) = (d, -k/d) (当k为负时) (d1, d2) = (-d, k/d) (当k为负时) 对每种情况检查d1和d2是否同奇偶 如果同奇偶,计算m和n,检查是否都是非负整数 记录所有满足条件的m²中的最小值
- 1
信息
- ID
- 3533
- 时间
- 3000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者