math - 如果我们已经知道 GCD(a, b)，我们如何找到 GCD(k + a, k + b)？

Question

我想知道是否可以在恒定时间内计算上述目标。我需要它来解决 codechef 上的问题。

Answer 1

只知道是不可能gcd(a+k,b+k)在恒定时间内计算的gcd(a,b)。

假设c,d是任意两个具有 的自然数d < c。

让

a = d - d = 0
b = c - d
k = d

然后我们O(1)及时知道

gcd(a,b) = gcd(0, c - d) = c - d

如果我们可以gcd(a+k,b+k) = gcd(c,d)在O(1)额外的时间内计算，那么我们可以及时计算所有gcd O(1)，这是不可能的。

说了这么多，当然有可能在某些感兴趣的情况下，知识gcd(a,b)可能会导致gcd(a+k,b+k)比其他情况更快的计算。