POW（）函数给出错误的结果

-1

3^(3^1000000000) mod 1000000007

这样做的结果是：930782551

但这样做直接在Python花费大量的时间，和该程序挂起：

return pow(3,pow(3,1000000000),1000000007)

所以，我认为执行这将是相同的：

return pow(3,pow(3,1000000000, 1000000007),1000000007)

但结果是：270196661

我怎样才能在合理的时间正确的结果930782551？

你的WA表达应该是'（3 ^（（3^1000000000）mod1000000007））mod1000000007'。你放在那里和你放在这里的东西是不一样的。 –

寻求调试帮助的问题（“为什么这个代码不工作？”）必须包含所需的行为，特定的问题或错误以及在问题本身中重现问题所需的最短代码。没有明确问题陈述的问题对其他读者无益。见[mcve]。 –

你需要费马小定理/欧拉定理来有效地做到这一点。幸运的是，1000000007是素数，所以很容易计算它的总体函数。 –

根据你的问题你的编辑，使用

>>> pow(3, pow(3, 1000000000, 500000003), 1000000007) 
930782551

其他任何东西都将永远需要计算。这个表达式是用费马小定理得到的。

我问了一个关于math.stackexchange.com的问题。以下是一步一步的细分：https://math.stackexchange.com/a/2317797/454045。

底线pow不显示不正确的结果。这是绝对正确的。你的意见是错误的。

希望这可以消除任何混淆。

2017-06-10 21:44:37

一旦我证实1000000007是素数，我只是做了pow（3，pow（3,1000000000,1000000006），1000000007）' –

我不知道费马定理，所以我不得不问一个问题。 x） –

费马小定理是一个美丽的数论，它不难理解。一旦你有了这些，证明欧拉定理并不难。当你有_that_时，你可以了解RSA加密如何工作。 –

编辑

起初我还以为是sintaxis的问题，所以我回答：

return pow(3,pow(3,1000000000),1000000007)

但这需要不合理的时间量。所以我试图解决计算时间的问题，但我没有及时做到这一点:)。

完美的答案是@Coldspeed之一，他能解决计算时间问题好了，整个解释是有

2017-06-10 20:48:41

你知道需要多长时间来计算吗？ –

这会打破 –

@ Don'tcallme这是真的，在真正的开始我只是认为这是一个麻烦的问题，但更多的是，我投了这个问题，因为它真的很有趣，我希望你接受这个版本 –

回答