مضروب العدد مع باقي القسمة

خطوات الاستخدام

الخطوة 1: فهم المسألة. مضروب العدد (n!) هو حاصل ضرب جميع الأعداد الصحيحة الموجبة من 1 إلى n. المطلوب هو حساب n! mod m، أي باقي قسمة n! على m. هذا الحساب شائع في التوافقيات ونظرية الأعداد والتشفير لتجنب الأعداد الكبيرة جداً.

الخطوة 2: مدخلات المستخدم. أدخل قيمة n (عدد صحيح غير سالب) وقيمة m (عدد صحيح موجب، عادة ما يكون أقل من 2^31). كلما زادت n، كلما زاد حجم n! بسرعة، لذا فإن الحساب المباشر قد يسبب تجاوزاً في البيانات. لذلك نستخدم عملية باقي القسمة بعد كل ضرب (modulo arithmetic) للحفاظ على الأرقام ضمن نطاق آمن.

الخطوة 3: الطريقة الحسابية. نستخدم خوارزمية تكرارية: نبدأ بـ result = 1 (لأن 0! = 1). ثم من i = 1 إلى n: نضرب result في i، ثم نأخذ باقي القسمة على m: result = (result * i) % m. هذه العملية تضمن أن النتيجة دائماً بين 0 و m-1، وتتجنب الأعداد الكبيرة. التعقيد الزمني هو O(n).

الأسئلة الشائعة

حساب n! مباشرة يؤدي إلى أعداد ضخمة جداً بسرعة. فمثلاً 20! يتكون من 19 رقماً، و100! يتكون من 158 رقماً، مما يتسبب في تجاوز سعة التخزين (overflow) في الحواسيب حتى مع أنواع البيانات كبيرة السعة. لذلك نستخدم عملية باقي القسمة بعد كل ضرب للحفاظ على النتائج ضمن نطاق m. هذه الطريقة شائعة في البرمجة التنافسية وحسابات التوافقيات حيث نحتاج إلى نتائج معيارية لحساب التوافيق (nCr) والمعاملات ذات الحدين. كما أنها أساسية في التشفير الحديث مثل خوارزمية RSA التي تعمل ضمن مجال معياري. علاوة على ذلك، في نظرية الأعداد، استخدام modulo يسمح لنا بتطبيق نظريات مثل نظرية فيرما ونظرية ويلسون التي تسهل الحسابات.

عندما يكون n ضخماً، الخوارزمية التكرارية البسيطة تكون بطيئة (تعقيد O(n)). ولكن يمكننا الاستفادة من خواص عامل m. إذا كان m عدداً أولياً و n >= m، فإن الناتج هو 0 مباشرة. أما إذا كان m مركباً، فقد نستخدم خوارزمية تعتمد على تحليل m إلى عوامل أولية واستخدام نظرية الباقي الصيني لحساب n! mod كل عامل على حدة، ثم دمج النتائج. أيضاً، يمكن تجميع الضربات في دورات (periodicity) حيث أن n! mod m يصبح دورياً بعد فترة معينة، خاصة إذا كان m عدداً أولياً صغيراً. تقنية أخرى هي استخدام خوارزمية Wilson's theorem للتحقق من العوامل الأولية. في الحالات العملية التي يكون فيها n في حدود 10^7 أو أقل، التكرار المباشر مقبول، أما للأكبر نستخدم التحسينات.

نظرية ويلسون تنص على أن: إذا كان p عدداً أولياً، فإن (p-1)! ≡ -1 (mod p). بمعنى آخر، (p-1)! mod p = p-1. هذه النظرية مفيدة في اختبار الأولية وحساب العوامل الأولية. بالنسبة لحاسبة factorial modulo، يمكن استخدامها لتسريع الحساب عندما يكون m أولياً و n = m-1، حيث نعرف النتيجة فوراً. أيضاً، إذا كان n < p، فيمكن استخدام هذه العلاقة بالتزامن مع نظرية تقسيم المضروب إلى أجزاء (مثل نظرية لوجاندر) لحساب n! mod p. لكن تطبيقها المباشر يتطلب n قريباً من m. في التطبيقات العملية، تُستخدم نظرية ويلسون لإثبات النتائج بدلاً من الحسابات العددية المباشرة.

لا توجد صيغة مغلقة بسيطة لـ n! mod m عندما يكون m مركباً، وذلك لأن سلوك n! modulo m يعتمد على بنية m التحليلية. يمكن تقسيم m إلى عوامل أولية q_i^e_i، ثم حساب n! mod كل منها باستخدام خوارزميات خاصة مثل خوارزمية Lucas للأعداد الأولية الصغيرة، أو نظرية Legendre لمعرفة قوى الأعداد الأولية داخل n!. بعد ذلك نجمع النتائج باستخدام نظرية الباقي الصيني (CRT). هذه العملية معقدة وتتطلب برمجة متقدمة، لذا في الحاسبات البسيطة نستخدم التكرار المباشر لـ n الصغير نسبياً. بالنسبة للمسائل النظرية، يمكن إثبات أن n! mod m يكون 0 إذا احتوى m على عامل أولي أصغر من أو يساوي n، بشرط أن تكون أسس العوامل كافية.

مضروب العدد مع باقي القسمة

أدخل القيم

خطوات الاستخدام

أمثلة محلولة

أمثلة محسوبة

الأسئلة الشائعة

أدخل القيم

خطوات الاستخدام

حاسبات ذات صلة

1احسب 10! mod 7

2احسب 8! mod 15

أمثلة محسوبة

الأسئلة الشائعة