問題描述

我想編寫代碼來計算 pow(a,b)%MOD 的值.我使用 C++ 編寫代碼.

I want to code for calculating the value of pow(a,b)%MOD. I use C++ to code.

但問題是 b 的值可能非常大.我知道 log(b) 時間復雜度方法.但是，b 的值可能不適合 C++ 的long long"數據類型.例如 b 可以是第 1000000000 個斐波那契數.這么大的數字要精確計算本身是不可能的(在時間限制內).

But the problem is the value of b can be very large. I know the log(b) time complexity method. But, the value of b might not fit in the data type "long long" of C++. For example b can be 1000000000 th Fibonacci number. Exact calculation of such a big number is itself, not possible (in time limits).

附言:

• pow(a,b) 表示 a*a*a*a*... b 次.
• X % MOD 表示 X 除以 MOD 所得的余數.

推薦答案

這是一個典型的任務.請(或者，真的，請！)閱讀Euler 的 totient 函數.

That's a typical task. Please (or, really, PLEASE!) read about the Euler's totient function.

然后是 歐拉定理.

問題是你可以將 a^b 顯著減少到 a^(b % phi(MOD)).是的，您將需要某種整數分解方法，但仍然沒有關于實際計算所需功率的瘋狂想法.

The thing is you can dramatically reduce a^b to a^(b % phi(MOD)). Yes, you will need some kind of an integer factorization method, but still, no crazy ideas about actually calculating the power needed.

我們年輕時手工制作了這樣的樣本 :) 即使數字遠遠超出 32/64 位范圍.

We did such samples by hand in my youth :) Even when the numbers where far beyond 32/64 bit range.

嗯，你生活和學習.2008年得到的結果:

Well, you live and learn. In 2008 the result is obtained:

totient 是 gcd 的離散傅立葉變換:(Schramm (2008))"

"The totient is the discrete Fourier transform of the gcd: (Schramm (2008))"

所以計算 phi(b) 不需要知道它的因數.

So to calculate phi(b) one does not need to know its factors.

編輯(2):

Carmichael 的函數是您需要計算的任何 a、b 和 MOD 的正確答案.

And the Carmichael's function is what you need to calculate to get the correct answer for any a, b and MOD.

這篇關于計算 (a^b)%MOD的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網！