我一直在尝试确定一种计算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
(a^n-b^n)可以简化为https://math.stackexchange.com/questions/406703/how-to-simplify-an-bn。但找不到(a^n+b^n)的版本
在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
尝试使用以下方法优化求幂:
我看到了两种加速代码的方法。在
首先,利用数学事实
(如果},然后加上这些模
s
不为零)。所以你不需要完整地计算a**n + b**n
,你只需要它的模a - b
。你可以找到(a**n) % (a-b)
和{a - b
。在现在,通过exponentiation by squaring method找到{}。这涉及执行
log2(n)
次的循环。在循环的每一次传递中,取余数moda - b
,以保持数字较低并加快计算速度。在这就是你的算法。在每一步通过平方和模的幂运算求出}。然后把它们加起来,再取一次模量。最后,用
(a**n) % (a-b)
和{a - b
找到该值的GCD。在在某些情况下,例如
a - b
prime,我可以看到一些快捷方式。正如你所注意到的,一个数的幂的模是重复的。然而,对于a - b
的大值,找出它们何时重复是一个非常重要的问题,特别是当a - b
是复合的并且很难计算因素时。除非您有关于a - b
值和其他参数的其他信息,否则我建议您不要使用重复。如果a
和b
的值很小且事先已知(如a = 100
和b = 4
的示例中所示),则重复更吸引人,并且可以预先计算幂模96
的值。在与其使用这段代码,不如使用Python的内置pow函数。See here作为文档。给@DSM的帽子提示。在
根据请求,这里是我的例行程序,通过将给定数的模平方来求幂。当然,还有一些变化可以做。这个版本在参数上没有错误检查,并且为了提高效率做了一些小的调整。在
^{pr2}$相关问题 更多 >
编程相关推荐