الحسابيات المعيارية (Modular Arithmetic)

الحسابيات المعيارية هي طريقة للقيام بالعمليات الحسابية حيث “تدور” الأعداد بعد الوصول إلى قيمة معينة — تسمى المعامل (modulus).

فكر بها مثل الساعة. بعد 24 ساعة، تعود الساعة لنفس الوقت مرة أخرى. هذه هي عملية mod 24!

معنى “mod”

عندما نقول a mod m، فهذا يعني الباقي عند قسمة a على m.

مثال:

التعبير المعنى النتيجة
7 mod 3 7 ÷ 3 → الباقي 1
10 mod 4 10 ÷ 4 → الباقي 2
15 mod 6 15 ÷ 6 → الباقي 3
12 mod 12 12 ÷ 12 → الباقي 0

في C++ نستخدم %:

#include <iostream>
using namespace std;

int main() {
    cout << 7 % 3 << endl;   // 1
    cout << 10 % 4 << endl;  // 2
    cout << 10 % 5 << endl;  // 0
}

استخدام الحسابيات المعيارية في البرمجة

عند التعامل مع أعداد كبيرة جدًا (مثلًا في التوافقيات أو التشفير)، قد تصبح النتائج أكبر من أن تتسع لأنواع البيانات العادية. الحل: نأخذ كل شيء mod لنبقي النتائج صغيرة.

المعامل الشائع في البرمجة التنافسية:

const int MOD = 1'000'000'007; // عدد أولي كبير

لماذا نستخدمه:

  • يناسب الأعداد 64-بت بأمان.
  • تجنب تجاوز السعة عند الجمع.
  • لأنه عدد أولي، له خصائص رياضية مفيدة.

قواعد أساسية

  1. الجمع
(a + b) % m = (a % m + b % m) % m
  1. الطرح
(a - b) % m = ((a % m - b % m) + m) % m

نضيف +m لضمان عدم الحصول على عدد سالب.

  1. الضرب
(a * b) % m = (a % m * b % m) % m

مثال:

int a = 7, b = 5, m = 3;
cout << (a + b) % m << endl;   // 0
cout << (a * b) % m << endl;   // 2

مثال: جمع أعداد كبيرة

#include <iostream>
using namespace std;

int main() {
    const int MOD = 1'000'000'007;
    long long a = 1e12, b = 1e12;
    cout << (a + b) % MOD << endl;
}

الناتج:

999999979

التعامل مع الأعداد السالبة

في C++، % قد يعطي نتيجة سالبة:

cout << (-5) % 3; // -2

لحل هذه المشكلة:

((a % m) + m) % m

مثال:

int a = -5, m = 3;
cout << ((a % m) + m) % m; // 1

الأسس المعيارية (Modular Exponentiation)

لحساب (a^b m) بطريقة سريعة، لا تضرب (a) (b) مرة. استخدم الأس السريع:

  • إذا كان \((b)\) زوجيًا: \((a^b = (a^{b/2})^2)\)
  • إذا كان \((b)\) فرديًا: \((a^b = a \cdot (a^{b/2})^2)\)
long long modpow(long long a, long long b, long long m) {
    if (b == 0) return 1;

    long long half = modpow(a, b / 2, m);
    long long res = (half * half) % m;

    if (b % 2 == 1)
        res = (res * (a % m)) % m;
    
    return res;
}

نظرًا لأن \(b\) يتم تقسيمه إلى النصف في كل مرة يتم فيها استدعاء التكرار، فإن العدد الإجمالي للمكالمات التكرارية هو \(\lfloor \log_2 b \rfloor + 1\)، وبالتالي فإن التعقيد الزمني لهذه الدالة هو \(O(\log b)\).

مثال للاستخدام:

cout << modpow(2, 10, 1000); // الناتج 24

المعكوس المعياري (Modular Inverse)

عند الحاجة للقيام بالقسمة تحت المودولو، نستخدم المعكوس المعياري.

إذا كان MOD أوليًا، معكوس a:

\(a^{-1} \equiv a^{MOD-2} \mod MOD\)

int inverse = modpow(a, MOD - 2, MOD);

القسمة تصبح:

(a * modpow(b, MOD - 2, MOD)) % MOD

متى نستخدم الحسابيات المعيارية؟

  • عند التعامل مع أعداد كبيرة جدًا
  • عندما يحتاج الناتج فقط “mod 1e9+7”
  • عند تنفيذ خوارزميات رياضية (أس، معكوس، توافقيات)

الملخص السريع

  • % يعطي الباقي عند القسمة
  • استخدم (a + b) % MOD, (a * b) % MOD, و ((a - b) % MOD + MOD) % MOD
  • للأسس الكبيرة استخدم الأس السريع (modular exponentiation)
  • للقسمة استخدم المعكوس المعياري إذا كان المودولو أوليًا