मॉड्युलर अंकगणित

बहुत से मौकों पर हमें गणनाओं के पूर्ण मान से ज़्यादा, उनके किसी विशेष संख्या m से विभाजन के बाद के शेष (मॉड्युलो) में दिलचस्पी होती है। यानी, हमें किसी गणना का परिणाम m से भाग लेने के बाद मिलने वाले रिमेंडर में चाहिए होता है।

असल में, हम रोज़ाना मॉड्युलर अंकगणित का इस्तेमाल करते हैं। जब भी हम घड़ी देखकर समय पता करते हैं, तो हमें ब्रह्मांड की शुरुआत से गुज़रा पूरा समय नहीं चाहिए होता, बल्कि दिन का वह घंटा चाहिए होता है, जो 12 या 24 घंटों के चक्र में है। जैसे-जैसे समय आगे बढ़ता जाता है, घड़ी 0 से 1, फिर 2, 3, …, 11 तक जाती है और वापस 0 पर आ जाती है। ये सिलसिला अनंत तक चलता रहता है, और इस दौरान घड़ी पर दिखाई देने वाला घंटा हमेशा 0 से 11 के बीच होता है। अगर किसी साल की शुरुआत से गुज़रे घंटों की संख्या h दी गई हो, तो दिन के वर्तमान घंटे का पता h % 12 (यानी 12 से भाग देने पर मिलने वाले शेष) से लगाया जा सकता है।

अगर हमें किसी संख्या का आखिरी अंक चाहिए, तो इसे आप 10-अंकीय “घड़ी” जैसा समझ सकते हैं, जिसके अंक 0 से 9 तक होते हैं। जब आप किसी संख्या को 1 से बढ़ाते हैं, तो उसका आखिरी अंक भी 0 से 9 तक घूमकर वापस 0 हो जाता है। किसी भी संख्या n का आखिरी अंक निकालने के लिए n % 10 का इस्तेमाल किया जा सकता है (10 से भाग देने पर मिलने वाला शेष)।

इसी तरह, अगर हमें बाइनरी (0 और 1) से जुड़े काम करने हों, तो इसे 2-अंकीय “घड़ी” मान सकते हैं जिसमें सिर्फ़ 0 और 1 होते हैं। 0 में 1 जोड़ने पर 1 मिलता है, लेकिन 1 में 1 जोड़ने पर वह दोबारा 0 हो जाता है। किसी भी बिट-स्ट्रिंग वाली संख्या n का आखिरी बिट जानने के लिए n % 2 (2 से भाग देने पर मिलने वाला शेष) निकाला जा सकता है।

इसलिए, मॉड्युलर अंकगणित असल में m बिंदुओं वाली एक घड़ी जैसा ही है (घंटों के लिए m = 12, अंकों के लिए m = 10 और बिट्स के लिए m = 2)। m कोई भी संख्या हो सकती है। कई समस्याओं में किसी बड़ी प्राइम संख्या जैसे पर मॉड्युलो लेना ज़रूरी होता है, ताकि गणनाओं को वास्तव में पूरा करना पड़े और उन्हें आसान तरीक़े से बाइपास न किया जा सके।

Addition modulo m

अगर हम दो संख्याओं a और b को जोड़ रहे हैं, तो कई बार हमें सिर्फ़ उनके योग का मॉड्युलो m चाहिए होता है। उदाहरण के लिए, अगर हमें सिर्फ़ योग का आखिरी अंक चाहिए, तो हम वास्तव में सिर्फ़ (योग) % 10 में दिलचस्पी रखते हैं। इसे और भी आसान बनाने के लिए, हम पहले a और b का मॉड्युलो m ले सकते हैं और उसके बाद उन्हें जोड़कर दोबारा मॉड्युलो m ले सकते हैं। इससे गणना सरल हो जाती है res = (a % m + b % m) % m:

Subtraction modulo m

मॉड्युलो m में a से b घटाने को इस तरह सोच सकते हैं जैसे घड़ी को b घंटे पीछे घुमाया जा रहा हो, जो फिलहाल a पर है। उदाहरण के लिए, 5 से 2 घंटे पीछे जाने पर (5 - 2) % 12 = 3 मिलता है, या 5 से 7 घंटे पीछे जाने पर (5 - 7) % 12 = -2 % 12 = 10 मिलता है। अगर घटाने वाली संख्या m से बड़ी हो, तब भी पहले उसका मॉड्युलो m ले सकते हैं: (21 % 10 - 18 % 10) % 10 = (1 - 8) % 10 = 3:

कुछ भाषाओं (जैसे Python) में % ऑपरेटर का परिणाम हमेशा धनात्मक आता है, लेकिन कुछ अन्य भाषाओं (जैसे C++) में ऐसा नहीं होता। ऐसी भाषाओं में, अगर अंतिम परिणाम नकारात्मक हो जाए, तो हमें उस पर m जोड़ना पड़ सकता है (उदाहरण के लिए, -2 में 12 जोड़कर 10 मिला), ताकि हम “घड़ी को एक पूरा चक्कर आगे” बढ़ाकर सही डिस्प्ले-मान पा सकें।

Multiplication modulo m

जब हम दो संख्याओं का गुणा कर रहे हों और हमें परिणाम मॉड्युलो m चाहिए, तब भी हम पहले दोनों का मॉड्युलो m ले सकते हैं, फिर गुणा कर सकते हैं, और अंत में दोबारा मॉड्युलो m ले सकते हैं। अगर m = 10 है, तो यह मूल रूप से दो संख्याओं کے अंतिम अंक को गुणा करके उस उत्पाद का आखिरी अंक जानने जैसा ही है:

Division modulo m

गुणा, जोड़ और घटाने की तुलना में मॉड्युलर विभाजन (डिवीज़न) करना ज़्यादा चुनौतीपूर्ण है। आखिरी अंक के संदर्भ में सोचें, अगर 28 को 7 से बाँटें, तो परिणाम 4 आता है और आखिरी अंक 4 होता है। लेकिन अगर हम 28 का आखिरी अंक (8) और 7 का आखिरी अंक (7) देखें, तो 8÷7 से सीधे 4 तक पहुँचना आसान नहीं होता। मॉड्युलो m में विभाजन करने के लिए आम तौर पर ऑयलर के सिद्धांत (Euler’s theorem) का इस्तेमाल किया जाता है। इसका विस्तार से विवरण यहाँ पढ़ा जा सकता है: https://cp-algorithms.com/algebra/module-inverse.html

Challenge: Calculate the power modulo m

आपको की गणना करनी है, जहाँ इनपुट में आपको x, n, और m दिए जाते हैं।

इनपुट

इनपुट में तीन पूर्णांक x, n (1 ≤ n ≤ ), और m (1 ≤ x, m ≤ ) होते हैं।

आउटपुट

कार्यक्रम को का परिणाम प्रिंट करना चाहिए।

उदाहरण