快速求模幂：二进制法 |
您所在的位置：网站首页 › 迭代次幂的逆运算 › 快速求模幂：二进制法 |
快速求模幂：二进制法
|
参考wiki Modular exponentiation bm mod n 这个当很大时很难计算，所以可以用到二进制法来求模幂 直接举例
我们再优化一下，指数等于 0是没有必要乘的，但是我们任然需要计算基数，方便下一个直接平方
我们来总结一下： 每一步都有两个操作 (假如幂是1执行，是0直接执行第二步)：基数(记为B) X 前一位的结果就 (记为R) R=(B*R) mod n基数B平方且mod n为下一次作准备 B=B2 mod n 算法C++ #include using namespace std; typedef unsigned long long ll; ll* d2t(ll num) //10进制转为2进制 { ll *temp = new ll[100]; int b_num = 0; do { temp[b_num] = num % 2; //存取的 0-n 代表低-高 num = (num - temp[b_num]) / 2; b_num++; } while (num); temp[b_num] = 2; // 加入结束符号2 检测时遇到2就结束 return temp; } int returnsize(ll *temp) //检验数量 { int num = 0; while (temp[num++] != 2); return num - 1; } ll getmodpow(ll base, ll *binary, int m, int num) //计算模幂 { ll result = 1; for (int i = 0; i |
可以看出前一个基数的幂是后一个基数幂的平方，所以我们假设第一个基数为b1，第二个为b2，依次类推 
现在我们合并一下，即每个先乘以低位mod的结构，再mod 
其实上面每次算基数时，我们仍然可以mod 497
【本文地址】