एल्गोरिथ्म्स और डेटा स्ट्रक्चर्स

बाइनरी एक्सपोनेंशिएशन

मान लीजिए आपके पास 3 संख्याएँ x, n, और m हैं। आपको का परिणाम निकालना है।

इनपुट

केवल एक पंक्ति में 3 पूर्णांक x, n, और m (1 ≤ x, n, m ≤ ) दिए जाते हैं।

आउटपुट

कार्यक्रम को अभिव्यक्ति का परिणाम निकालना और प्रदर्शित करना चाहिए।

उदाहरण

इनपुट
आउटपुट
2 10 5
4

विवरण

  1. 2^10 = 1024 ⇒ 1024 mod 5 = 4
 

ट्यूटोरियल

क्योंकि सभी संख्याएँ काफी बड़ी हो सकती हैं, हमें एक तेज़ एल्गोरिदम की आवश्यकता है ताकि परिणाम को जल्दी निकाला जा सके। बाइनरी एक्सपोनेंशिएशन बड़ी शक्तियों (powers) को कुशलता से गणना करने की एक प्रभावी विधि है। यह आवश्यक गुणा-कार्यों की संख्या को कम कर देता है, इस वजह से पारंपरिक विधि (जिसमें 1 से n तक हर बार x से गुणा करते जाते हैं) की तुलना में ज़्यादा तेज़ चलता है।
 
बाइनरी एक्सपोनेंशिएशन निम्नलिखित गणितीय सिद्धांत पर आधारित है: अगर किसी संख्या x को n घात तक उठाना हो, तो को इस प्रकार बाँटा जा सकता है:
  • जब n सम हो
  • जब n विषम हो
इससे गणना तेज़ हो जाती है, क्योंकि हम एक बार की गणना करके उसी परिणाम को स्वयं से गुणा कर सकते हैं। एल्गोरिदम का खाका इस तरह दिख सकता है:
def binpow(x, n, m):
    if n == 0:                        # बेस केस: x^0 = 1
        return 1
    if n % 2 == 0:                    # n सम है => आधा निकालें और गुणा करें
        half = binpow(x, n // 2, m)   # आधा निकालें
        return (half * half) % m      # परिणाम = x^(n/2) * x^(n/2)

    # n विषम है => परिणाम = x * x^(n-1)
    return (x * binpow(x, n - 1, m)) % m
बाइनरी एक्सपोनेंशिएशन की मदद से समय जटिलता से घटकर हो जाती है, क्योंकि हम n को प्रत्येक चरण में (जब यह सम होता है) आधा करते जाते हैं। साथ ही, जब भी n विषम होता है, अगले चरण में वह सम हो जाता है।
आइए कुछ उदाहरणों पर इस एल्गोरिदम को देख लें:
x = 2, n = 10 (सरलता के लिए यहाँ m को अनदेखा कर रहे हैं)
  1. [n = 10] → n % 2 == 0 ⇒ binpow(2, 5) की गणना करें
  1. [n = 5] → n % 2 ≠ 0 ⇒ 2 * binpow(2, 4) लौटाएँ
  1. [n = 4] → n % 2 == 0 ⇒ binpow(2, 2) की गणना करें
  1. [n = 2] → n % 2 == 0 ⇒ binpow(2, 1) की गणना करें
  1. [n = 1] → n % 2 ≠ 0 ⇒ 2 * binpow(2, 0) लौटाएँ
  1. [n = 0] → n == 0 ⇒ 1 लौटाएँ
  1. [n = 1] पर वापस आने पर ⇒ 2 * 1 = 2
  1. [n = 2] पर वापस आने पर ⇒ 2 * 2 = 4
  1. [n = 4] पर वापस आने पर ⇒ 4 * 4 = 16
  1. [n = 5] पर वापस आने पर ⇒ 2 * 16 = 32
  1. [n = 10] पर वापस आने पर ⇒ 32 * 32 = 1024
 
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue