计算（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 th斐波纳契数。这种大数的精确计算本身是不可能的（在时间限制上）。

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得到的余数。

推荐答案

这是一个典型的任务。请（或真的，请您阅读）了解欧拉的功能。

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.

EDIT（2）：

并且 Carmichael的功能是您需要计算以获得任何答案的正确答案， 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屋！