Prime के Modulo में काम करना

प्रतियोगिताओं में उत्तर बहुत बड़े हो सकते हैं, यहाँ तक कि अन्य जगहों पर उपलब्ध पूर्णांक प्रकारों की सीमा से भी कहीं आगे। इसलिए समस्याएँ परिणाम को किसी बड़े अभाज्य के मॉड्यूलो में माँगती हैं, ताकि संख्याएँ छोटी रहें। 🔢

आपको सबसे अधिक दिखाई देने वाली अभाज्य संख्या 1000000007 है, जिसे अक्सर 1e9+7 लिखा जाता है। यह टकरावों से बचने के लिए पर्याप्त बड़ी और 64 बिट में समाने के लिए पर्याप्त छोटी है।

मॉड्यूलो संक्रियक भाग देने के बाद बचा हुआ शेषफल देता है। इसलिए 17 % 5 का परिणाम 2 है, क्योंकि 17 को 5 से भाग देने पर 2 शेष बचता है।

आप पहले जोड़ सकते हैं और अंत में मॉड ले सकते हैं, या जोड़ते समय ही मॉड लेते जा सकते हैं। दोनों तरीकों में शेषफल समान रहता है, इसलिए संख्याओं को छोटा रखने के लिए बार-बार मॉड लीजिए।

यही नियम गुणा पर भी लागू होता है: गुणनफल का अभाज्य संख्या से मॉड लीजिए। Python बड़े पूर्णांकों को मूल रूप से संभालता है, लेकिन मॉड लेने से प्रत्येक मान बहुत छोटा और तेज़ रहता है।

लंबे लूप में प्रत्येक पुनरावृत्ति पर % MOD लागू कीजिए। इससे संख्याएँ बहुत बड़ी होने से रुकती हैं और प्रत्येक संक्रिया सस्ती तथा पूर्वानुमानित रहती है।

कई भाषाओं में घटाव से ऋणात्मक शेषफल मिल सकता है। अंतिम मॉड लेने से पहले MOD वापस जोड़ दीजिए, ताकि परिणाम सुरक्षित 0 वाली सीमा में आ जाए।

अच्छी खबर है: धनात्मक मॉड्यूलस के लिए Python का % पहले से ही गैर-ऋणात्मक परिणाम देता है। इसलिए -1 % 7 का परिणाम -1 नहीं, बल्कि 6 होता है और आपको अलग से सुधार नहीं करना पड़ता।

मुख्य विचार यह है: जोड़ और गुणा के लिए (a op b) % m का परिणाम (a%m op b%m) % m के बराबर होता है। इससे आप इनपुट को मिलाने से पहले ही छोटा कर सकते हैं।

जोड़, घटाव और गुणा मॉड के अंतर्गत ठीक से काम करते हैं। लेकिन साधारण भाग ऐसा नहीं करता, और इसके लिए आपको इस पाठ्यक्रम में आगे मॉड्यूलर प्रतिलोम की आवश्यकता होगी।

अपने समाधान की शुरुआत में MOD को एक स्थिरांक के रूप में परिभाषित कीजिए। कोड में 1000000007 को कई जगह लिखने के बजाय एक नामित मान रखना बेहतर है, क्योंकि बिखरे हुए लेखन में टाइपिंग की गलती छिप सकती है।

अब आप 1e9+7 जैसे अभाज्य मॉड्यूलस की सहायता से बहुत बड़ी गिनतियों को छोटा रख सकते हैं। प्रत्येक चरण पर जोड़, घटाव और गुणा को घटाइए, ऋणात्मक परिणामों का ध्यान रखिए और भाग को प्रतिलोमों के लिए सुरक्षित रखिए। 🎯