الرفع السريع للقوى بترديد
حساب القوى باستخدام pow(a, b, m)
الرفع السريع للقوى بترديد درس مجاني في Competitive Programming Academy على CoddyKit. هذا هو الدرس 2 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Competitive Programming Academy، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
مشكلة الأسس
تحتاج كثيرًا إلى رفع عدد إلى أس هائل، مع إبقاء كل شيء تحت modulo. أما ضرب العامل مرة تلو الأخرى فسيتطلب عددًا كبيرًا جدًا من الخطوات. ⚡
الطريقة الساذجة بطيئة جدًا
تعمل حلقة الضرب b مرة في O(b) خطوة. ومع أس يقترب من مليار، سيتجاوز ذلك حد الوقت قبل أن ينتهي.
for _ in range(b): r = r * a % MODربّع لتصعد أسرع
الحيلة هي التربيع: a مرفوعًا للقوة 8 يساوي ((a تربيع) تربيع) تربيع. يضاعف كل تربيع قيمة الأس، لذا تصل إلى أسس هائلة في خطوات قليلة.
اقرأ الأس بالصيغة الثنائية
كل أس هو مجموع قوى العدد 2، أي صيغته الثنائية. لذلك تضرب فقط في قوى الأساس التي تكون بتاتها مفعّلة، وتتجاوز الباقي.
# 13 = 1101 -> a^8 * a^4 * a^1افحص البت الأدنى
افحص b & 1 لاختبار البت الأدنى. إذا كانت قيمته 1، فادمج الأساس الحالي في النتيجة المتراكمة قبل المتابعة.
if b & 1: result = result * base % MODزِح وربّع في كل دورة
بعد كل بت، ربّع الأساس وأزح الأس إلى اليمين بمقدار واحد. لا تتكرر الحلقة إلا نحو 30 إلى 60 مرة لأي مُدخل واقعي.
base = base * base % MOD
b >>= 1جمع الأجزاء معًا
ابدأ result بالقيمة 1، ثم كرر ما دام الأس موجبًا. تُسمّى فكرة الأسّ السريع هذه أيضًا الأسّ الثنائي أو الرفع بالتربيع.
result = 1
while b > 0:
if b & 1: result = result*base%MOD
base = base*base%MOD
b >>= 1تعمل في زمن لوغاريتمي
بما أن كل دورة تقسم الأس إلى النصف، تكون التكلفة O(log b). يحوّل ذلك مليار عملية ضرب إلى نحو ثلاثين فقط، ضمن أي حد زمني تقريبًا.
يوفّر لك Python الدالة pow
نادرًا ما تكتب الحلقة بنفسك، إذ تنفذ الدالة المدمجة في Python، وهي pow(a, b, m)، الأسّ السريع modulo بسرعة C الخالصة.
print(pow(2, 100, MOD))لماذا يهم ذلك قريبًا
الأسّ السريع هو المحرك وراء المعكوس modulo باستخدام مبرهنة فيرما، التي ستتعرف إليها بعد قليل. أتقنه الآن، فتصبح القسمة تحت modulo سهلة.
افحص الأساس أولًا
اختزل الأساس باستخدام base % MOD قبل الحلقة. فالأساس الأكبر من modulus سيؤدي لولا ذلك إلى تضخيم كل خطوة تربيع.
base = a % MODتحقق سريع
ما سرعة الأسّ السريع modulo؟
مراجعة
يمكنك الآن رفع الأعداد إلى أسس هائلة في O(log b) باستخدام التربيع وقراءة البتات. وفي Python، استدعِ pow(a, b, m) وانتقل إلى ما يلي. 🚀
الأسئلة الشائعة
هل درس «الرفع السريع للقوى بترديد» مجاني؟
نعم — نص درس «الرفع السريع للقوى بترديد» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Competitive Programming Academy، انتقل إلى CoddyKit PRO. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
ماذا ستتعلم في «الرفع السريع للقوى بترديد»؟
حساب القوى باستخدام pow(a, b, m) تتمرن على Competitive Programming Academy مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Competitive Programming Academy؟
لا تُشترط خبرة سابقة. Competitive Programming Academy على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 2 من أصل 4.
كم من الوقت يستغرق درس «الرفع السريع للقوى بترديد»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Competitive Programming Academy هذا؟
نعم. كل درس في Competitive Programming Academy يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- العمل بترديد عدد أولي
- الرفع السريع للقوى بترديد
- المعكوس الترديدي باستخدام فيرما
- nCr باستخدام المضروبات المحسوبة مسبقًا