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這是真的，在真正的開始我只是認爲這是一個麻煩的問題，但更多的是，我投了這個問題，因爲它真的很有趣，我希望你接受這個版本 –

回答