计算给定 z 的 z³ = x²y² 的整数解数

我研究这个问题已经有一段时间了。这个问题要求找出两个数x和y，使x和y的平方的乘积等于k的立方。我的方法是解出x，假设输入1会得到一个数lim，当平方等于k的立方时。代码首先测试函数arg的平方根是否为整数。如果不是，则返回0。如果没有，则找到lim。然后，代码遍历一段数字i，从1开始直到lim的平方根，测试lim和i的商是否为整数。由于问题要求除数的数量，我发现最好使用reduce并计算成功的x和y对的数量，而不是遍历列表以查找其大小。

def c(k: Long) = {
val sqrtk = math.sqrt(k)
sqrtk.isWhole match {
case false => 0
case true =>
val lim = k * sqrtk
(1 to math.sqrt(lim).toInt).foldLeft(0)((acc, i) =>
if ((lim / i).isWhole) acc + 2 else acc
)
}
}

我很确定问题在于使用两个平方根和正在执行的除法，但到目前为止我还无法使这段代码执行得更好。最初我甚至无法通过基本的测试，现在我可以通过大约48个随机测试，并且希望接近通过所有的测试。我已经尝试了许多其他的解决方案，包括制作我自己的平方根函数，并试图找到所有素数的除数等，但没有一个像我上面发布的代码那么快。正如标题所说，这段代码是用Scala编写的。

事先感谢您提供的任何帮助。

注意:

x^2、y^2的组合必须为整数值。
这个问题的固定测试有33个k值，其中最大的是10000000095。到目前为止，这些测试之后是多达48个随机k值。允许完成所有k值的最大时间为16秒，并且在完成所有测试之前超时。

解决方案:解决这个问题所需的洞察力是z³和x²y²因子之间的关系。在这种情况下，k的平方根的因子，结合表达式(3 * e1 + 1) *…* (3 * eN + 1)，给出了问题的解决方案。

def c(k: Long) = {
val sqrtk = math.sqrt(k)
@annotation.tailrec
def factorList(x: Long, n: Long = 2, ls: List[Long] = Nil): List[Long] = {
n * n > x match {
case false if x % n == 0 => factorList(x / n, n, n :: ls)
case false               => factorList(x, n + 1, ls)
case true                => x :: ls
}
}
sqrtk.isWhole match {
case false => 0
case true =>
factorList(sqrtk.toLong)
.groupBy(identity)
.map { case (_, v) => 3 * v.size + 1 }
.product
}
}

正如我在评论中提到的，任何时候你将sqrt()与整数进行比较，即使逻辑是正确的，你也可能偏离轨道。

在这个问题的数学中有一些线索。首先，所有东西都是相乘的，没有任何加法。这意味着什么?LHS的质因数必须是RHS的质因数。此外，我们知道每个因子的计数必须相同。

那么你就需要考虑10B的极限值的素数因子，这是一个很大的素数数。我们可以看到LHS是三次的，所以我们知道任何质数在z^3的分解中必须出现3次。10B的立方根仍然很大，但可以迭代。但是在x, y, z的幂之间有一个微妙的关系。z为立方，x和y均为平方，因此因子a不可能只出现3次。事实上，它必须出现6次(LCM = 2,3)才能出现。

所以，我们只需要考虑到10B^(1/6)的质因数，也就是~ 68，或者大约20个因数。

这个工作，是在python中编写的，但应该很容易映射到scala。它在不到550ms的时间内测试100K个随机试验

代码:

#prime factorize
# solving z^3 = y^2 * x^2
from random import randint

def test(k):
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, ]
if k==1 : return 1, {}
# factor k^3
k = k**3
factors = {}  # a dictionary mapping of prime:occurrences ...
for p in primes:
while k % (p**6) == 0:
factors[p] = factors.get(p,0) + 1
k /= p**6
if k == 1: break
if k != 1: return 0, {}
# now loop through the factors & counts to construct possible pairs.
# for each occurrence of each factor, we can put 0, 1, 2, ..., count*3 occurrences in "x"
# so if there is 1 occurrence, we can put 0, 1, 2, 3 multiples of the factor in the first digit
# or, more generally, 3 * count + 1
if len(factors) == 0:
return 0, {}
tot = 1
for v in factors.values():
tot *= 3*v+1
return tot, factors

for k in (1, 4, 16, 2019, 4096576, 10_000_000_000):
print(k, test(k))
# test over randomized list
vals = [randint(1,10_000_000_000) for _ in range(100_000)]
for val in vals:
result = test(val)
if result[0]:
print(val, result)

输出:

1 (1, {})
4 (4, {2: 1})
16 (7, {2: 2})
2019 (0, {})
4096576 (160, {2: 3, 11: 1, 23: 1})
10000000000 (0, {})
[Finished in 563ms]

这是一个简单的方法:

z * z * z = x * x * y * y表示z * sqrt(z) = x * y
如果sqrt(z)不是整数，它是无理数，因此有0个解
否则，设q = sqrt(z)为整数平方根。
将q = f1^e1 * ... fN^eN分解为质因数f_i和正整数指数e_i。
然后x * y = f1^(3 * e1) * ... * fN^(3 * eN)

(3 * e1 + 1) * ... * (3 * eN + 1)

x

y

那么，假设某种分解算法factorize，它将是:

def c(k: Long): Long = {
val q = math.sqrt(k).toLong
if (q * q == k) {
val fs = factorize(q)
fs.map(e => 3 * e._2 + 1).product
} else {
0
}
}

完整的代码与一个过于简单的factorize:

def c(k: Long): Long = {
val q = math.sqrt(k).toLong
if (q * q == k) {
val fs = factorize(q)
fs.map(e => 3 * e._2 + 1).product
} else {
0
}
}
@main def main(): Unit = {
println(c(1))
println(c(4))
println(c(4096576))
println(c(2019))
}
def factorize(i: Long): List[(Long, Int)] = {
var odd = i
var twoExp = 0
while (odd % 2 == 0) {
odd /= 2
twoExp += 1
}
def factorizeRec(n: Long, divisor: Long, limit: Long): List[(Long, Int)] = {
require(n >= 3)
var unfactoredPart = n
var e = 0
while (unfactoredPart % divisor == 0) {
unfactoredPart /= divisor
e += 1
}
if (unfactoredPart == 1) {
if (e > 0) {
List((divisor, e))
} else {
Nil
}
} else {
if (e > 0) {
val newLimit = (math.sqrt(unfactoredPart).toInt + 1)
(divisor, e) :: factorizeRec(unfactoredPart, divisor + 2, newLimit)
} else {
factorizeRec(unfactoredPart, divisor + 2, limit)
}
}
}
val sqrtLim = (math.sqrt(i).toInt + 1)
val unevenFactors = 
if (odd >= 3) then factorizeRec(odd, 3, sqrtLim) 
else Nil
if (twoExp > 0) {
(2, twoExp) :: unevenFactors
} else {
unevenFactors
}
}

打印

。我没有测试它是否足够快，也没有费心去注册。

如果这仍然太慢，那就在某处偷波拉德的Rho。

代码:

相关内容

最新更新

热门标签：