我一直在尝试确定一种用于计算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
（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
我看到两种加快代码速度的方法。
首先，使用数学事实
gcd(r, s) = gcd(r % s, s)
（如果s不为零）。因此，您无需进行全部计算a**n + b**n，只需对它取模即可a - b。然后，您可以找到(a**n) % (a-b)并(b**n) % (a-b)添加这些模数来完成此操作a - b。
现在，发现a**n由通过平方方法幂。这涉及执行log2(n)时间的循环。在循环的每一遍中，取余数moda - b以保持较低的数字并加快计算速度。
所以有您的算法。查找(a**n) % (a-b)并(b**n) % (a-b)通过求幂通过在每个步骤平方和模量。然后添加它们并再次取模数。最后，使用查找该值的GCD a - b。
在某些情况下，例如a - b素数，我可以看到一些快捷方式。正如您所注意到的，数的幂的模数确实会重复。但是，对于的大值，找出它们何时重复并不容易a - b，特别是如果a - b是复合且难以分解的情况。除非您有关于和的值a - b以及其他参数的其他信息，否则建议您不要使用重复。如果值a和b小且预先知道（在你的例子a = 100和b = 4中，重复是更有吸引力，你可以预先计算的权力模量的值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
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句