मान लीजिए कि हमें a^b mod 1337 की गणना करनी है जहां a एक धनात्मक पूर्णांक है और b एक सरणी के रूप में दिया गया एक अत्यंत बड़ा धनात्मक पूर्णांक है। तो अगर a =2 और b =[1,0] तो आउटपुट 1024
. होगाइसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
पावरमॉड () विधि को परिभाषित करें जो आधार और शक्ति लेती है
-
मी :=1337, सेवानिवृत्त :=1
-
जबकि पावर 0 नहीं है
-
यदि शक्ति विषम है, तो रिट :=रिट * बेस मॉड m
-
आधार:=आधार^2 मॉड एम
-
शक्ति :=शक्ति/2
-
-
वापसी रिट
-
सुपरपावर () को परिभाषित करें, इसमें ए और बी लगते हैं
-
अगर b =0 का आकार है, तो 1
. लौटाएं -
अंतिम :=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
