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