计算(a ^ b)%MOD

Question

我想编码用于计算pow(a,b)%MOD的值.我使用C++进行编码.

但问题是b的值可能非常大.我知道log(b)时间复杂度方法.但是,b的值可能不适合C++的"long long"数据类型.例如,b可以是1000000000个斐波那契数.这样一个大数字的精确计算本身是不可能的(在时间限制内).

PS:

• pow(a,b)表示a*a*a*a*... b次.
• X%MOD表示通过MOD除以X得到的余数.

Answer 1

这是一项典型的任务.请(或者,真的,请!)阅读有关欧拉的赋能函数.

然后是欧拉定理.

事情是你可以大大减少a ^ b到^(b%phi(MOD)).是的,你需要某种整数分解方法,但仍然没有关于实际计算所需功率的疯狂想法.

我年轻时手工制作了这样的样品:)即使数字远远超过32/64位范围.

编辑:嗯,你生活和学习.2008年的结果是:

"总是gcd的离散傅立叶变换:( Schramm(2008))"

因此,为了计算phi(b),不需要知道它的因素.

EDIT(2):

并且Carmichael的函数是你需要计算的,以获得任何a,b和MOD的正确答案.