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