计算（a ^ b）％MOD
我想编写计算pow（a，b）％MOD的值。 我使用C ++来编码。
但问题是b的价值可以非常大。 我知道日志（二）时间复杂性的方法。 但是，b的值可能不适合C ++的“long long”数据types。 例如b可以是10亿次斐波那契数。 精确计算这样一个大数字本身是不可能的（在时间限制内）。
PS：
- pow（a，b）表示a * a * a * a * … b次。
- X％MOD表示MOD除以X得到的余数。
这是一个典型的任务。 请（或者，真的，请！）读到欧拉的总function 。
然后是欧拉定理 。
事情是你可以大幅度减lessa ^ b到^（b％phi（MOD））。 是的，你将需要某种整数分解方法，但是对于实际计算所需的功率还没有疯狂的想法。
我们在年轻时候手工做了这样的样本:)甚至当数字远远超过了32/64位的范围。
编辑：好吧，你生活和学习。 2008年的结果是：
“总数是gcd的离散傅里叶变换：（Schramm（2008））”
所以计算phi（b）不需要知道它的因素。
EDIT（2）：
Carmichael的function就是你需要计算的，以获得任何a，b和MOD的正确答案。
对于处理非常大的数字，请看一下boost的Multiprecision库。 它有一个powm（）函数可以很好地用于这个目的。
来自通用整数操作 ：
template <class Integer> Integer powm(const Integer& b, const Integer& p, const Integer& m);退货b p ％m。
例：
#include <boost/multiprecision/cpp_int.hpp> boost::multiprecision::cpp_int pow("8912627233012800753578052027888001981"); boost::multiprecision::cpp_int mod("0x86f71688cdd2612c117d1f54bdae029"); boost::multiprecision::cpp_int base(12345); boost::multiprecision::cpp_int result = powm(base, pow, mod); std::cout << "result is: " << result << std::endl;
打印：
result is: 5758534182572671080415167723795472693
第一：在C / C ++中^ 不是权力的运算符。 实际上，这个没有运营商。 ^表示一个按位XOR 。 你必须使用pow(base, exp) ，它可以在头文件math.h或cmath 。
对于如此巨大的数字，使用double或long double （精确的长度和结果数据types可能取决于您的平台），但在某些时候，您会偶然发现精确性问题，所以根据您的使用情况，值的大小，您最好的select可能会使用自定义数据types（编辑：例如，从其中一个链接问题中find的库中的一个）。
我build议使用专门的math库。 另外这看起来像encryption，所以我build议使用encryption库。 GNU必然会有一个你可以使用的。 这是因为在许多情况下，在encryption中，可以select指数来使用普通math库不能假设的快捷方式进行有效的计算。
我使用这个函数来解决这个问题
UVA 374 – 大Mod
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=310
// a^b % T // with Exponentiation by squaring (http://en.wikipedia.org/wiki/Exponentiation_by_squaring#Basic_method) // if a very large use // R=(unsigned long long)(R*a)%T; int restOfPot(long long a,int b,int T) { a%=T; long long R=1; while(b) { if(b&1) R=(R*a)%T; a=(a*a)%T; b>>=1; } return int(R); }
但是，b的值可能不适合C ++的“long long”数据types。 例如b可以是10亿次斐波那契数。
对于这样的事情，有一个简单的解决方法：召回
a ^（b + c）== a ^ b * a ^ c mod d
您可以使用与计算斐波纳契数字相同types的recursion来计算您询问的特定产品 – 您根本不需要大数目或模数求幂！
有时出现的另一个版本是
a（b * c）=（a ^ b）^ c模d
#include <iostream> #include <math.h> #include <stdint.h> using namespace std; int main(){ int64_t a, b, k, d; cin >> a >> b >> k; int64_t poew = pow(a, b); d = poew % k; cout << d; }
因为int64_t比int的范围更大
