المعكوس الترديدي باستخدام فيرما

يتصرف الجمع والطرح والضرب بصورة سليمة تحت modulus، لكن القسمة العادية لا تعمل كذلك. لا يمكنك ببساطة إجراء القسمة ثم حساب الباقي. ⚠️

الحل هو المعكوس modulo: تتحول القسمة على x إلى الضرب في معكوس x. لذلك تتحول a / b modulo m إلى a مضروبة في معكوس b.

معكوس x هو العدد الذي يعطي 1 عند ضربه في x تحت modulus. وهو يؤدي دور 1/x في الحساب العادي.

يوجد المعكوس فقط عندما لا يشترك x وm في أي عامل. ويضمن استخدام modulus أولي مثل 1e9+7 وجود معكوس لكل x غير صفري.

تنص مبرهنة فيرما الصغرى على أنه بالنسبة إلى عدد أولي p، يكون x مرفوعًا للقوة p ناقص 1 مكافئًا لـ 1 modulo p، ما دام x ليس من مضاعفات p.

افصل عاملًا واحدًا من x، ولا بد أن يكون الجزء المتبقي معكوسه. لذلك فإن معكوس x هو x مرفوعًا للقوة p ناقص 2، مع حساب modulo p.

ذلك الأس هائل، لذا استخدم الأسّ السريع من الدرس السابق. وفي Python، ينفذ استدعاء واحد لـ pow المهمة كاملة.

لحساب a مقسومًا على b تحت modulo، اضرب a في معكوس b. يكون الباقي هو حاصل القسمة الحقيقي modulo p تمامًا.

لا يوجد معكوس لـ 0، إذ لا يعطي ضرب أي عدد في الصفر القيمة 1. تحقّق من عدم القسمة على قيمة تختزل إلى الصفر تحت modulus.

كل معكوس وفق مبرهنة فيرما هو عملية أسّ سريع واحدة، لذا تبلغ تكلفته O(log p). وهذا رخيص لعدد قليل من عمليات القسمة، لكنه يتراكم عند إجراء الملايين منها.

عندما تحتاج إلى معكوسات كثيرة، احسبها مسبقًا بمرور خطي ذكي بدلًا من استدعاء pow لكل عنصر. ستعتمد على ذلك عند حساب nCr لاحقًا.

أي قوة تعطي المعكوس modulo عند استخدام modulus أولي؟

يمكنك الآن إجراء القسمة تحت modulus أولي بالضرب في المعكوس modulo، المحسوب على صورة x مرفوعًا للقوة p ناقص 2 باستخدام pow. فقط لا تحسب معكوس الصفر أبدًا. ✅