Scala实现z³=x²y²整数解计数超时问题求助

首先明确数学推导，修正思路偏差：

题目要求整数对(x,y)满足 (x^2 y^2 = k^3)，等价于 ((xy)^2 = k^3)。这意味着 (k^3) 必须是完全平方数，即 (k) 的质因数分解中每个指数都必须是偶数（因为 (3 \times e) 为偶数 → (e) 为偶数），也就是 (k) 必须是完全平方数。若 (k) 不是完全平方数，直接返回0。

当 (k) 是完全平方数时，设 (m = \sqrt{k})，则 (k^3 = m^6 = (m³⁾2)，因此 (xy = \pm m^3)。此时整数对(x,y)的总数由以下部分组成：

• 正整数对：(xy = m^3)，数量等于 (m^3) 的正约数个数 (d(m^3))
• 负负整数对：(xy = m^3)（x负、y负），数量同样为 (d(m^3))
• 正负整数对：(xy = -m^3)（x正、y负），数量为 (d(m^3))
• 负正整数对：(xy = -m^3)（x负、y正），数量为 (d(m^3))

总数量为 (4 \times d(m^3))。

而 (d(m^3)) 可通过质因数分解计算：若 (m = p_1^{e_1} \times p_2^{e_2} \times ... \times p_n^{e_n})，则 (m^3 = p_1^{3e_1} \times p_2^{3e_2} \times ... \times p_n^{3e_n})，其正约数个数为 ((3e_1 + 1) \times (3e_2 + 1) \times ... \times (3e_n + 1))。

你的当前实现存在两个核心问题：

1. 正确性问题：仅统计了 (m^3) 的正约数个数（甚至在 (m^3) 是平方数时多算1个），完全忽略了符号组合，导致结果远小于正确值。
2. 性能问题：遍历到 (\sqrt{m^3}) 对于大 (m) 来说时间复杂度极高（比如 (m=1e5) 时，(\sqrt{m^3}=1e7.5)，遍历次数达千万级），必然超时。

优化后的代码实现 #

import java.math.BigInteger

def c(k: Long): Long = {
  // 精确判断k是否为完全平方数，避免Double精度丢失
  val kBig = BigInteger.valueOf(k)
  val sqrtResult = kBig.sqrtAndRemainder()
  if (sqrtResult(1).signum() != 0) return 0
  
  val m = sqrtResult(0).longValue()
  var temp = m
  var divisor = 2L
  var count = 1L
  
  // 质因数分解m，计算(3e+1)的乘积
  while (divisor * divisor <= temp) {
    if (temp % divisor == 0) {
      var exponent = 0
      while (temp % divisor == 0) {
        exponent += 1
        temp /= divisor
      }
      count *= (3 * exponent + 1)
    }
    divisor += 1
  }
  
  // 处理剩余的质因数
  if (temp > 1) {
    count *= (3 * 1 + 1)
  }
  
  // 乘以4得到所有整数对的数量
  count * 4
}

优化点说明 #

1. 精确判断完全平方数：
   使用BigInteger的sqrtAndRemainder方法，避免了Double对大整数的精度丢失问题（比如大于 (2^{53}) 的整数无法用Double精确表示），确保判断结果准确。

2. 质因数分解替代遍历约数：
   试除法分解质因数的时间复杂度为 (O(\sqrt{m}))，而 (m = \sqrt{k})，因此实际遍历的上限是 (\sqrt{\sqrt{k}} = k^{1/4})。对于 (k=1e10)，(k^{1/4}=100)，遍历次数极少，完全不会超时。

3. 直接计算约数个数：
   通过质因数的指数直接计算 (d(m^3))，避免了枚举所有约数的操作，时间复杂度骤降。

4. 修正计数逻辑：
   乘以4得到所有符号组合的整数对数量，符合题目对整数x、y的要求。

内容的提问来源于stack exchange，提问作者Hooahclitus