समस्या
base^exponent mod modulus निकालिए। exponent 10^18 तक हो सकता है, इसलिए base से उतनी बार गुणा करना असंभव है; इसकी बजाय वर्ग करके घात निकालने की विधि (exponentiation by squaring) अपनाइए: exponent के बाइनरी अंकों को देखिए, हर कदम पर आधार का वर्ग कीजिए, और जब अंक 1 हो तो उसे परिणाम में गुणा कर दीजिए। यहाँ के किसी भी exponent के लिए इसमें लगभग 60 कदम लगते हैं।
modular_exponentiation(base, exponent, modulus) लिखिए।
शुरुआत में ही base को modulus के modulo में छोटा कर लीजिए, और हर गुणा के बाद भी। चूँकि modulus ≤ 10^9 है, ऐसे दो छोटे किए गए मानों का गुणनफल 10^18 से कम रहता है और signed 64-bit integer में आ जाता है।
इनपुट
base: आधार।
exponent: वह घात जिस तक आधार को उठाना है।
modulus: वह संख्या जिससे शेषफल लेना है।
आउटपुट
base^exponent mod modulus लौटाइए, जो 0 से modulus − 1 तक का कोई मान होगा। हर base के लिए base^0 को 1 मानिए, 0 के लिए भी, इसलिए exponent 0 होने पर उत्तर 1 mod modulus है।
सीमाएँ
0 ≤ base ≤ 10^18
0 ≤ exponent ≤ 10^18
1 ≤ modulus ≤ 10^9
उदाहरण
इनपुट:
base = 3
exponent = 13
modulus = 50
अपेक्षित आउटपुट:
expected = 23
इनपुट:
long long base = 3;
long long exponent = 13;
long long modulus = 50;
अपेक्षित आउटपुट:
long long expected = 23;
इनपुट:
long base = 3;
long exponent = 13;
long modulus = 50;
अपेक्षित आउटपुट:
long expected = 23;
व्याख्या
3^13 = 1,594,323, और 1,594,323 = 50 × 31,886 + 23, इसलिए उत्तर 23 है।
इनपुट:
base = 2
exponent = 10
modulus = 1000
अपेक्षित आउटपुट:
expected = 24
इनपुट:
long long base = 2;
long long exponent = 10;
long long modulus = 1000;
अपेक्षित आउटपुट:
long long expected = 24;
इनपुट:
long base = 2;
long exponent = 10;
long modulus = 1000;
अपेक्षित आउटपुट:
long expected = 24;
व्याख्या
2^10 = 1024, और 1024 mod 1000 = 24।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
exponent को सबसे निचले बिट से शुरू करके एक-एक बाइनरी अंक करके देखिए।
संकेत 2
हर कदम पर आधार का वर्ग कीजिए, और जब मौजूदा बिट 1 हो तो उसे परिणाम में गुणा कीजिए।
संकेत 3
परिणाम को 1 % modulus से शुरू कीजिए, ताकि modulus 1 होने पर उत्तर 0 आए।
अपेक्षित जटिलता
समय O(log exponent), अतिरिक्त स्थान O(1)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।