➕ Модулна аритметика: Теория и Практика

📜 Дълбока теория на Модулната аритметика

Модулната аритметика е аритметика на остатъците. Когато кажем $A <equiv B \pmod M$, имаме предвид, че $A$ и $B$ дават един и същ остатък при деление на $M$, или еквивалентно: $M$ дели разликата $(A - B)$.

Свойства на конгруенциите

Рефлексивност: $A <equiv A \pmod M$.
Симетричност: Ако $A <equiv B \pmod M$, то $B <equiv A \pmod M$.
Транзитивност: Ако $A <equiv B$ и $B <equiv C$, то $A <equiv C \pmod M$.
Събиране/Умножение: Можем да събираме и умножаваме конгруенции.
Ако $A <equiv B$ и $C <equiv D$, то $A+C <equiv B+D$ и $A \cdot C <equiv B \cdot D \pmod M$.

🚀 Бързо модулно степенуване (Modular Exponentiation)

Пресмятането на $A^B \pmod M$ наивно отнема $O(B)$ време, което е бавно за $B \approx 10^{18}$. Използваме метода на "двоичното повдигане" (Binary Exponentiation), който работи за $O(\log B)$.

Идея: $A^{2k} = (A^k)^2$ и $A^{2k+1} = A \cdot (A^k)^2$.

long long power(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = (__int128)res * base % mod; // Използваме __int128 за избягване на overflow при умножението
        base = (__int128)base * base % mod;
        exp /= 2;
    }
    return res;
}

Забележка: Ако mod е до $10^9$, long long е достатъчен. Ако mod е до $10^{18}$, междинното умножение може да препълни long long, затова се ползва __int128.

↔ Разширен алгоритъм на Евклид (Extended Euclidean Algorithm)

Алгоритъмът намира цели числа $x$ и $y$, удовлетворяващи уравнението на Безу: $$A \cdot x + B \cdot y = \gcd(A, B)$$

Как работи (Стъпка по стъпка): Знаем, че $\gcd(A, B) = \gcd(B, A \% B)$. Нека сме намерили $x_1, y_1$ за двойката $(B, A \% B)$, т.е.: $$B \cdot x_1 + (A \% B) \cdot y_1 = \gcd(A, B)$$ Заместваме $A \% B = A - \lfloor A/B \rfloor \cdot B$: $$B \cdot x_1 + (A - \lfloor A/B \rfloor \cdot B) \cdot y_1 = \gcd$$ $$A \cdot y_1 + B \cdot (x_1 - \lfloor A/B \rfloor \cdot y_1) = \gcd$$ Следователно новите коефициенти са: $x = y_1$ и $y = x_1 - \lfloor A/B \rfloor \cdot y_1$.

long long extendedGCD(long long a, long long b, long long &x, long long &y) {
    if (a == 0) {
        x = 0; y = 1;
        return b;
    }
    long long x1, y1;
    long long gcd = extendedGCD(b % a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return gcd;
}

➗ Модулно деление и Обратен елемент

Делението $A / B \pmod M$ се дефинира като $A \cdot B^{-1} \pmod M$. Обратният елемент $B^{-1}$ съществува само ако $\gcd(B, M) = 1$.

Намиране на $B^{-1}$:

Ако $M$ е просто: Според Малката теорема на Ферма, $B^{M-2} \pmod M$.
Ако $M$ не е просто: Използваме разширения Евклид за решаване на $B \cdot x + M \cdot y = 1$. Тук $x$ е търсеният обратен елемент (може да е отрицателен, затова взимаме $(x \% M + M) \% M$).

🇨🇳 Китайска теорема за остатъците (Chinese Remainder Theorem - CRT)

Позволява възстановяване на число $x$, ако знаем остатъците му при деление на няколко взаимно прости числа.

Система: $$x <equiv a_1 \pmod {m_1}$$ $$x <equiv a_2 \pmod {m_2}$$ ... $$x <equiv a_k \pmod {m_k}$$

Нека $M = m_1 \cdot m_2 \cdot \dots \cdot m_k$. Решението е уникално по модул $M$ и се дава от формулата: $$x = \left( \sum_{i=1}^{k} a_i \cdot M_i \cdot y_i \right) \pmod M$$ Където $M_i = M / m_i$, а $y_i$ е модулното обратно на $M_i$ спрямо $m_i$ ($M_i \cdot y_i <equiv 1 \pmod {m_i}$).

Приложение: Използва се при работа с много големи числа, като операциите се извършват паралелно с малки модули и накрая резултатът се възстановява.

👩‍👧 Дискретен логаритъм (Baby-step Giant-step)

Задача: Да се намери $x$, такова че $a^x <equiv b \pmod m$. Това е трудна задача, но алгоритъмът Baby-step Giant-step я решава за $O(\sqrt{m} \log m)$.

Идея: Представяме $x = i \cdot k - j$, където $k = \lceil \sqrt{m} \rceil$. Уравнението става $a^{ik - j} <equiv b \implies (a^k)^i <equiv b \cdot a^j$. 1. Пресмятаме дясната част за всички $0 \le j < k$ и ги запазваме в хеш-таблица (Baby steps). 2. Пресмятаме лявата част за $i = 1, \dots, k$ и проверяваме за съвпадение в таблицата (Giant steps).

🧮 Модулен факториел и Биномиални коефициенти

Пресмятане на факториел по модул

За големи $N$, директното пресмятане на $N!$ е невъзможно. Използваме модулна аритметика.

long long factorialMod(int n, long long mod) {
    long long result = 1;
    for (int i = 2; i <= n; i++) {
        result = (result * i) % mod;
    }
    return result;
}

Биномиални коефициенти по модул

$\binom{n}{k} = \frac{n!}{k! \cdot (n-k)!}$. За пресмятане по модул използваме обратен елемент.

long long binomialMod(int n, int k, long long mod) {
    if (k > n) return 0;

    vector<long long> fact(n + 1);
    fact[0] = 1;
    for (int i = 1; i <= n; i++) {
        fact[i] = (fact[i-1] * i) % mod;
    }

    long long denominator = (fact[k] * fact[n - k]) % mod;
    long long inv = power(denominator, mod - 2, mod); // Използваме Ферма

    return (fact[n] * inv) % mod;
}

Триъгълник на Паскал

Алтернативен метод за малки $N$ и $K$ без използване на деление.

long long pascal[1005][1005];

void buildPascal(int maxN, long long mod) {
    for (int n = 0; n <= maxN; n++) {
        pascal[n][0] = 1;
        for (int k = 1; k <= n; k++) {
            pascal[n][k] = (pascal[n-1][k-1] + pascal[n-1][k]) % mod;
        }
    }
}

🔐 Теорема на Ойлер (Обобщение на Ферма)

За всяко число $A$ и $M$, където $\gcd(A, M) = 1$: $$A^{\phi(M)} \equiv 1 \pmod M$$ Където $\phi(M)$ е функцията на Ойлер (брой числа до $M$, взаимно прости с $M$).

Следствие: $A^{-1} \equiv A^{\phi(M) - 1} \pmod M$.

Функция на Ойлер (Euler's Totient)

int phi(int n) {
    int result = n;
    for (int p = 2; p * p <= n; p++) {
        if (n % p == 0) {
            while (n % p == 0) n /= p;
            result -= result / p;
        }
    }
    if (n > 1) result -= result / n;
    return result;
}

🎲 Генериране на случайни числа по модул

При работа с хеш функции и рандомизирани алгоритми често е нужно генериране на случайни числа.

#include <random>

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

long long randomMod(long long mod) {
    return uniform_int_distribution<long long>(0, mod - 1)(rng);
}

🔢 Модулна аритметика в матрици

Умножение на матрици по модул за бързо пресмятане на рекурентни зависимости.

Пример: N-то число на Фибоначи за O(log N)

typedef vector<vector<long long>> Matrix;

Matrix multiply(const Matrix& A, const Matrix& B, long long mod) {
    int n = A.size();
    Matrix C(n, vector<long long>(n, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod;
            }
        }
    }
    return C;
}

Matrix matrixPower(Matrix A, long long p, long long mod) {
    int n = A.size();
    Matrix result(n, vector<long long>(n, 0));
    for (int i = 0; i < n; i++) result[i][i] = 1; // Единична матрица

    while (p > 0) {
        if (p % 2 == 1) result = multiply(result, A, mod);
        A = multiply(A, A, mod);
        p /= 2;
    }
    return result;
}

long long fibonacci(long long n, long long mod) {
    if (n <= 1) return n;
    Matrix F = {{1, 1}, {1, 0}};
    F = matrixPower(F, n - 1, mod);
    return F[0][0];
}

🧩 Линейни диофантови уравнения

Уравнения от вида $Ax + By = C$.

Решение съществува само ако $\gcd(A, B)$ дели $C$.

bool linearDiophantine(long long A, long long B, long long C, long long &x, long long &y) {
    long long g = extendedGCD(A, B, x, y);
    if (C % g != 0) return false; // Няма решение

    // Мащабиране на решението
    x *= C / g;
    y *= C / g;
    return true;
}

Общо решение: Ако $(x_0, y_0)$ е едно решение, то всички решения са: $$x = x_0 + \frac{B}{\gcd(A, B)} \cdot t$$ $$y = y_0 - \frac{A}{\gcd(A, B)} \cdot t$$ Където $t$ е произволно цяло число.

🏪 Задача: Размяна на пари (Coin Change)

Имаме монети с номинали $c_1, c_2, \ldots, c_k$ и искаме да разменим сума $S$. Колко начина има?

Решение с динамично програмиране по модул

long long coinChange(vector<int>& coins, int S, long long mod) {
    vector<long long> dp(S + 1, 0);
    dp[0] = 1;

    for (int coin : coins) {
        for (int i = coin; i <= S; i++) {
            dp[i] = (dp[i] + dp[i - coin]) % mod;
        }
    }

    return dp[S];
}

🎯 Задача: Степенна кула (Power Tower)

Пресметнете $A^{B^{C^{\ldots}}} \pmod M$.

Теорема: Ако $B \ge \log_2 M$, то $A^B \equiv A^{(B \bmod \phi(M)) + \phi(M)} \pmod M$.

long long powerTower(long long a, long long b, long long mod) {
    if (mod == 1) return 0;
    if (b == 0) return 1;

    long long phi_m = phi(mod);
    long long exp = powerTower(a, b - 1, phi_m);

    if (b > 1 && a >= log2(mod)) {
        exp += phi_m;
    }

    return power(a, exp, mod);
}

🌟 Често срещани модули в състезания

MOD = 1e9 + 7 (1000000007): Просто число, позволява използване на Малката теорема на Ферма.
MOD = 998244353: Просто число от вида $2^{23} \times 119 + 1$, има примитивен корен, полезно за NTT (Number Theoretic Transform).
MOD = 10^9 + 9: Друго просто число.

📝 Практически съвети

Винаги нормализирайте отрицателни числа:

int normalize(int x, int mod) {
    x %= mod;
    if (x < 0) x += mod;
    return x;
}

Внимавайте с overflow при умножение:

long long safeMul(long long a, long long b, long long mod) {
    return (__int128)a * b % mod;
}

Предпресметнете факториели и обратни: Когато имате много запитвания за биномиални коефициенти.

const int MAXN = 1000005;
const long long MOD = 1e9 + 7;
long long fact[MAXN], invFact[MAXN];

void precompute() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        fact[i] = fact[i-1] * i % MOD;
    }
    invFact[MAXN - 1] = power(fact[MAXN - 1], MOD - 2, MOD);
    for (int i = MAXN - 2; i >= 0; i--) {
        invFact[i] = invFact[i + 1] * (i + 1) % MOD;
    }
}

long long C(int n, int k) {
    if (k > n || k < 0) return 0;
    return fact[n] * invFact[k] % MOD * invFact[n - k] % MOD;
}

🧪 Задачи за практика

Степенуване: Пресметнете $A^B \bmod M$ за $B \le 10^{18}$.
Модулно деление: Пресметнете $\frac{A}{B} \bmod M$, където $M$ е просто.
Факториел: Пресметнете $N! \bmod M$ за $N \le 10^6$.
Биномиални коефициенти: Отговорете на $Q$ запитвания за $\binom{N}{K} \bmod M$.
Фибоначи: Намерете $N$-тото число на Фибоначи по модул $M$ за $N \le 10^{18}$.
Линейно уравнение: Решете $Ax \equiv C \pmod M$.
Дискретен логаритъм: Намерете $x$, такова че $A^x \equiv B \pmod M$.
Китайска теорема: Решете система от конгруенции.

🐀 Заключение

Модулната аритметика е в основата на алгоритмите за криптиране (RSA) и много състезателни задачи. Уверете се, че винаги обработвате отрицателните резултати правилно ((a % n + n) % n) и използвате long long за междинните изчисления. Бързото степенуване, обратният елемент и разширеният алгоритъм на Евклид са основни инструменти, които трябва да владеете перфектно. Китайската теорема за остатъците и теоремата на Ойлер разширяват възможностите за работа със сложни модулни задачи. Практикувайте редовно, за да развиете интуиция и скорост при решаване на задачи с модулна аритметика.