计算 (a^b)%MOD
我想编写代码来计算 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.
相关文章