สมมติว่าเราต้องคำนวณ 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
-
พลัง :=พลัง / 2
-
-
รีเทิร์น
-
กำหนด superPower() ซึ่งต้องใช้ a และ b
-
ถ้าขนาดของ b =0 ให้คืนค่า 1
-
สุดท้าย :=องค์ประกอบสุดท้ายของ b
-
ลบองค์ประกอบสุดท้ายออกจาก b
-
คืนค่า powerMod(พลังพิเศษ (a, b), 10) * powerMod (a, สุดท้าย)) 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
