GCD指数

2024-03-28 20:45:06 发布

您现在位置:Python中文网/ 问答频道 /正文

我一直在尝试确定一种计算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)的全局公式

注: 11<;=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的anwser之后,我在函数中通过如下所示的平方实现了求幂运算

我对上述解释的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 

平方求幂

^{pr2}$

Tags: 方法答案httpsltif数字mathabs
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(r, s) = gcd(r % s, s)

(如果s不为零)。所以你不需要完整地计算a**n + b**n,你只需要它的模a - b。你可以找到(a**n) % (a-b)和{},然后加上这些模a - b。在

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

这就是你的算法。在每一步通过平方和模的幂运算求出(a**n) % (a-b)和{}。然后把它们加起来,再取一次模量。最后,用a - b找到该值的GCD。在


在某些情况下,例如a - bprime,我可以看到一些快捷方式。正如你所注意到的,一个数的幂的模是重复的。然而,对于a - b的大值,找出它们何时重复是一个非常重要的问题,特别是当a - b是复合的并且很难计算因素时。除非您有关于a - b值和其他参数的其他信息,否则我建议您不要使用重复。如果ab的值很小且事先已知(如a = 100b = 4的示例中所示),则重复更吸引人,并且可以预先计算幂模96的值。在


与其使用这段代码,不如使用Python的内置pow函数。See here作为文档。给@DSM的帽子提示。在

根据请求,这里是我的例行程序,通过将给定数的模平方来求幂。当然,还有一些变化可以做。这个版本在参数上没有错误检查,并且为了提高效率做了一些小的调整。在

^{pr2}$

相关问题 更多 >