时间戳

首页 > 解决方案 > GCD 求幂

python - GCD 求幂

问题描述

我一直在尝试确定一种更短的计算 gcd((a^n + b^n), abs(ab)) 的方法。我注意到，如果我要计算（使用上面的公式）说 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), ab) 的简单公式，或者更好的是，我主要关心的是查找 (a^n + b^n) 的全局公式

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

  1. (a^n - b^n) 可以简化为https://math.stackexchange.com/questions/406703/how-to-simplify-an-bn。但找不到 (a^n + b^n) 的版本

  2. 按照 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

标签： pythongreatest-common-divisorexponentiation

解决方案

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

首先，使用以下数学事实

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

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

现在，a**n通过平方方法求幂。这涉及一个执行log2(n)时间的循环。在每次通过循环时，采用余数模式a - b以保持数字低并加快计算速度。

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

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

您可能应该使用 Python 的内置 pow 函数，而不是使用此代码。 有关文档，请参见此处。向@DSM 致敬。

根据要求，这是我通过对给定数字取模来求幂的例程。当然，可以做一些变化。这个版本不对参数进行错误检查，只是为了提高效率而进行了一些小操作。

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

推荐阅读