数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++中的超大数次幂
假设我们要计算 a^b mod 1337，其中 a 是一个正整数，而 b 是以数组形式给出的一个极大的正整数。所以，如果 a = 2，且 b = [1,0]，则输出为 1024
为了解决这个问题，我们将遵循以下步骤 −
定义 powerMod() 方法，它取基数和幂
m := 1337，ret := 1
当幂不为 0 时
如果幂为奇数，则 ret := ret * base mod m
base := base^2 mod m
power := power / 2
返回 ret
定义 superPower()，它取 a 和 b
如果 b 的大小为 0，则返回 1
last := b 的最后一个元素
从 b 中删除最后一个元素
返回 powerMod(superpower(a, b), 10) * powerMod(a, last)) mod 1337
示例 (C++)
让我们看一下以下实现，以获得更好的理解 −
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int powerMod(lli base, lli power){
lli mod = 1337;
lli ret = 1;
while(power){
if(power & 1) ret = (ret * base) % mod;
base = (base * base) % mod;
power >>= 1;
}
return ret;
}
int superPow(int a, vector<int>& b) {
if(b.size() == 0) return 1;
int last = b.back();
b.pop_back();
return (powerMod(superPow(a, b), 10) * powerMod(a, last)) % 1337;
}
};
main(){
Solution ob;
vector<int> v = {1,0};
cout << (ob.superPow(2, v));
}输入
2 [1,0]
输出
1024
更新于： 2020-05-02
412 个浏览量
广告