العمل بترديد عدد أولي

قد تكبر نتائج المسابقات كثيرًا، وتتجاوز بكثير سعة أي نوع أعداد صحيحة آخر. لذلك تطلب المسائل حساب النتيجة modulo عدد أولي كبير، للحفاظ على صغر الأعداد. 🔢

أكثر عدد أولي ستراه هو 1000000007، وغالبًا ما يُكتب 1e9+7. حجمه كبير بما يكفي لتفادي التصادمات، وصغير بما يكفي ليتسع له 64 بت.

يعطي عامل modulo الباقي بعد القسمة. لذلك فإن 17 % 5 تساوي 2، لأن 17 تترك باقيًا مقداره 2 عند قسمتها على 5.

يمكنك إجراء الجمع أولًا ثم حساب modulo في النهاية، أو حساب modulo أثناء التقدم. سيكون الباقي نفسه في الحالتين، لذا اختزل القيم باستمرار للحفاظ على صغرها.

تنطبق القاعدة نفسها على الضرب: احسب حاصل الضرب modulo العدد الأولي. يتعامل Python مع الأعداد الصحيحة الكبيرة تلقائيًا، لكن حساب modulo يحافظ على صغر كل قيمة وسرعة التنفيذ.

في الحلقة الطويلة، طبّق % MOD في كل تكرار. يمنع ذلك الأعداد من التضخم ويحافظ على رخص كل عملية وإمكانية توقع تكلفتها.

قد ينتج عن الطرح باقٍ سالب في العديد من اللغات. أضف MOD مجددًا قبل حساب modulo النهائي، بحيث تقع النتيجة في المجال الآمن من 0 إلى MOD - 1.

الخبر السار هو أن Python تعيد % نتيجة غير سالبة عند استخدام modulus موجب. لذلك تعطي -1 % 7 القيمة 6، لا -1، مما يوفر عليك عملية التصحيح.

الفكرة الأساسية: (a op b) % m تساوي (a%m op b%m) % m مع الجمع والضرب. يتيح لك ذلك اختزال المدخلات قبل دمجها.

يعمل الجمع والطرح والضرب بصورة سليمة تحت modulo، لكن القسمة العادية لا تعمل كذلك، وستحتاج لاحقًا في هذه الدورة إلى معكوس modulo لإجرائها.

عرّف MOD ثابتًا في بداية حلك. فقيمة واحدة مسماة أفضل من نثر 1000000007 في أنحاء الشيفرة، حيث قد يختبئ خطأ مطبعي.

لماذا نضيف MOD قبل حساب modulo لعملية طرح؟

يمكنك الآن الحفاظ على صغر الأعداد الكبيرة باستخدام modulus أولي مثل 1e9+7. اختزل الجمع والطرح والضرب في كل خطوة، وانتبه إلى القيم السالبة، واترك القسمة للمعكوسات. 🎯