GCD 求幂

Question

我一直在尝试确定一种更短的计算 gcd((a^n + b^n), abs(a-b)) 的方法。我注意到，如果我要计算（使用上面的公式）说 a = 100 和 b = 4，从 1 开始到 n 结束（一个循环），在某个点，答案变得不变。对于 a = 100、b = 4 和 n = 100，我创建了一个从 1 到 n 的循环，在每个点上，我应用公式，第一个答案 (n = 1) 是 8，此后它是 32，直到 n变为 100。为了优化，一旦找到两个相等的连续数字并且最新数字（此处为 32）成为答案，我就会跳出循环。有谁知道计算 gcd((a^n + b^n), a-b) 的简单公式，或者更好的是，我最关心的是找到 (a^n + b^n)

的全局公式

注意： 1. 1<=a,b,n<=10^12

(a^n - b^n)可以简化为https://math.stackexchange.com/questions/406703/how-to-simplify-an-bn。但是找不到 (a^n + b^n)
根据 Rory Daulton 的回答，我在函数中实现了如下所示的平方求幂

我的Python上面解释代码如下：

a, b, n = map(int, raw_input().split()); ans = -1

if a == b:
    ans = (a**n) + (b**n)

else:
    for j in xrange(n):
        x = gcd((a**n)+(b**n),abs(a-b))

        if x != ans:
            ans = x
        else:
            break
print ans

平方求幂

def pow3(x, n):
r = 1
while n:
    if n % 2 == 1:
        r *= x
        n -= 1
    x *= x
    n /= 2
return r

Answer 1

我看到了两种加速代码的方法。

首先，使用数学事实

gcd(r, s) = gcd(r % s, s)

（如果 s 不为零）。所以你不需要完全计算a**n + b**n，你只需要moduloa - b。你可以通过找到 (a**n) % (a-b) 和 (b**n) % (a-b) 然后添加那些 modulo a - b.

来做到这一点

现在，通过 exponentiation by squaring method 找到 a**n。这涉及一个执行 log2(n) 次的循环。在每次循环中，取余数 mod a - b 以保持较低的数字并加快计算速度。

所以有你的算法。在每一步通过平方和 modulus 求幂，求 (a**n) % (a-b) 和 (b**n) % (a-b)。然后添加它们并再次使用 modulus。最后，用 a - b 找到那个值的 GCD。

在某些情况下，比如a - b素数，我可以看到一些捷径。正如您所注意到的，mod数次方的 ulus 会重复出现。然而，对于较大的 a - b 值，找出它们何时重复是一个非常重要的问题，尤其是当 a - b 是复合的且难以分解时。除非您对 a - b 的值和其他参数有一些额外的信息，否则我建议您不要使用重复。如果 a 和 b 的值很小并且事先已知（如 a = 100 和 b = 4 的示例，则重复更有吸引力，您可以预先计算幂的值 modulus 96.

与其使用此代码，不如使用 Python 的内置 pow 函数。 See here 用于文档。向@DSM 致敬。

应要求，这是我通过 modulo 给定数字平方来求幂的例程。当然，可以做一些变化。此版本不会对参数进行错误检查，并且会稍微调整一下以提高效率。

def exp_by_squaring_mod(x, n, mod):
    """Calculate x**n % mod by squaring. This assumes x and n are non-
    negative integers and mod is a positive integer. This returns 1 for
    0**0.
    """
    result = 1
    x %= mod
    # Reduce n and keep constant the value of result * x**n % mod
    while n:  # while n is not zero
        if n & 1:  # n is odd
            result = result * x % mod
        x = x * x % mod
        n >>= 1  # integer divide by 2
    return result

Answer 2

尝试使用此方法优化求幂：

def powerBySquaring(x,n):
    if n < 0:
        x = 1 / x
        n = -n
    if n == 0: return 1
    y = 1
    while n > 1:
        if n % 2 == 0:
            x = x * x
            n = n / 2
        else:
            y = x * y
            x = x * x
            n = (n-1)/2
    return x * y

GCD 求幂

GCD Exponentiation

python

greatest-common-divisor

exponentiation

平方求幂