資料結構
網路
關係型資料庫管理系統
作業系統
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 個瀏覽量
廣告