计算 (a^b)%MOD [英] Calculating (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.

这篇关于计算 (a^b)%MOD的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！