問題描述
我想編寫代碼來計算 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模板網!