Skip to content

➗ Делимост и Алгоритъм на Евклид

Теорията на числата (Number Theory) е клон на математиката, който е дълбоко залегнал в информатиката. Разбирането на свойствата на целите числа, делимостта и остатъците е задължително за състезателното програмиране.

1. Признаци за делимост

Бърза проверка дали число \(N\) се дели на \(K\), без да извършваме делението (полезно при дълги числа).

  • 2: Последната цифра е четна (0, 2, 4, 6, 8).
  • 3: Сумата от цифрите се дели на 3.
  • 4: Числото, образувано от последните две цифри, се дели на 4.
  • 5: Последната цифра е 0 или 5.
  • 6: Дели се едновременно на 2 и на 3.
  • 8: Числото, образувано от последните три цифри, се дели на 8.
  • 9: Сумата от цифрите се дели на 9.
  • 10: Последната цифра е 0.
  • 11: Разликата между сумата на цифрите на нечетни позиции и сумата на тези на четни позиции се дели на 11 (или е 0).
    • Пример: 132 \(\to (1+2) - 3 = 0 \implies\) дели се.

2. Най-голям общ делител (НОД / GCD)

Най-голямото число, което дели без остатък едновременно \(A\) и \(B\).

2.1. Алгоритъм на Евклид

Това е един от най-старите и важни алгоритми. Базира се на факта, че \(\gcd(a, b) = \gcd(b, a \pmod b)\).

// Рекурсивен вариант
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

// Итеративен вариант
int gcd_iter(int a, int b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}
  • Вградена функция: В C++ (<algorithm> или <numeric>) има функция std::gcd(a, b) (от C++17) или __gcd(a, b) (GCC built-in, работи и в по-стари версии).

2.2. Свойства на НОД

  • \(\\gcd(a, b) = \gcd(a, b-a)\)
  • \(\\gcd(k \cdot a, k \cdot b) = k \cdot \gcd(a, b)\)
  • \(\\gcd(a, b, c) = \gcd(a, \gcd(b, c))\)

3. Най-малко общо кратно (НОК / LCM)

Най-малкото число, което се дели едновременно на \(A\) и \(B\). Формула: $\(\text{lcm}(a, b) = \frac{|a \cdot b|}{\gcd(a, b)}\)$

При програмиране, винаги първо делете, после умножавайте, за да избегнете препълване на типа: 

long long lcm(long long a, long long b) {
    if (a == 0 || b == 0) return 0;
    return (a / gcd(a, b)) * b;
}
* Вградена функция: std::lcm(a, b) (C++17).

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

Освен НОД, алгоритъмът може да намери и коефициентите \(x\) и \(y\) в уравнението на Безу (Bezout's identity): \(a \cdot x + b \cdot y = \gcd(a, b)\)

Това е ключово за намиране на Модулярно обратно число (Modular Inverse) при деление по модул.

int extended_gcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    int x1, y1;
    int d = extended_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}

6. Прости числа

Просто число е естествено число по-голямо от 1, което се дели само на 1 и себе си.

6.1. Проверка за простота - Наивен метод

bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;

    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    }
    return true;
}

Сложност: \(O(\sqrt{n})\) - проверяваме само до корен квадратен от n

6.2. Сито наЕратостен

За намиране на всички прости числа до N: 

vector<bool> sieve(int n) {
    vector<bool> prime(n + 1, true);
    prime[0] = prime[1] = false;

    for (int i = 2; i * i <= n; i++) {
        if (prime[i]) {
            for (int j = i * i; j <= n; j += i) {
                prime[j] = false;
            }
        }
    }
    return prime;
}

Сложност: \(O(n \log \log n)\) - много ефективно за множество проверки

6.3. Факторизация на число

Разлагане на число на прости множители: 

vector<pair<int, int>> primeFactors(int n) {
    vector<pair<int, int>> factors; // {прост делител, степен}

    for (int i = 2; i * i <= n; i++) {
        int count = 0;
        while (n % i == 0) {
            count++;
            n /= i;
        }
        if (count > 0) {
            factors.push_back({i, count});
        }
    }

    if (n > 1) {
        factors.push_back({n, 1}); // Останалото число е просто
    }

    return factors;
}

6.4. Брой делители

Използвайки факторизация: Ако \(n = p_1^{a_1} \cdot p_2^{a_2} \cdot ... \cdot p_k^{a_k}\), тогава: $\(d(n) = (a_1 + 1) \cdot (a_2 + 1) \cdot ... \cdot (a_k + 1)\)$

int countDivisors(int n) {
    int count = 1;

    for (int i = 2; i * i <= n; i++) {
        int exp = 0;
        while (n % i == 0) {
            exp++;
            n /= i;
        }
        count *= (exp + 1);
    }

    if (n > 1) count *= 2; // Останалото просто число

    return count;
}

6.5. Сума на делители

Формула: \(\sigma(n) = \frac{p_1^{a_1+1} - 1}{p_1 - 1} \cdot \frac{p_2^{a_2+1} - 1}{p_2 - 1} \cdot ...\)

long long sumOfDivisors(int n) {
    long long sum = 1;

    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int exp = 0;
            while (n % i == 0) {
                exp++;
                n /= i;
            }
            // Сума на геометрична прогресия: (p^(e+1) - 1) / (p - 1)
            sum *= (pow(i, exp + 1) - 1) / (i - 1);
        }
    }

    if (n > 1) sum *= (n + 1);

    return sum;
}

7. Модулярна аритметика - Основи

7.1. Модулярно събиране и умножение

long long modAdd(long long a, long long b, long long mod) {
    return ((a % mod) + (b % mod)) % mod;
}

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

7.2. Модулярно степенуване (Fast Exponentiation)

Изчисляване на \(a^b \bmod m\) за \(O(\log b)\): 

long long modPow(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;

    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exp /= 2;
    }

    return result;
}

7.3. Модулярно обратно (Modular Inverse)

Намиране на \(x\) такова че \((a \cdot x) \bmod m = 1\):

Метод 1: Използване на разширен Евклид 

long long modInverse(long long a, long long m) {
    int x, y;
    int g = extended_gcd(a, m, x, y);

    if (g != 1) return -1; // Обратното не съществува

    return (x % m + m) % m; // Нормализиране в положителен диапазон
}

Метод 2: За прости модули (по малка теорема на Ферма) 

long long modInverse(long long a, long long p) {
    // a^(-1) = a^(p-2) mod p, ако p е просто
    return modPow(a, p - 2, p);
}

8. Комбинаторни приложения

8.1. Факториел по модул

const int MOD = 1e9 + 7;
const int MAXN = 1e6;
long long fact[MAXN];

void precomputeFactorials() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        fact[i] = (fact[i-1] * i) % MOD;
    }
}

8.2. Биномни коефициенти C(n, k) = n! / (k! * (n-k)!)

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

    long long num = fact[n];
    long long den = (fact[k] * fact[n - k]) % mod;

    return (num * modInverse(den, mod)) % mod;
}

9. Китайска теорема за остатъците (CRT)

Решаване на система от конгруенции: - \(x \equiv a_1 \pmod{m_1}\) - \(x \equiv a_2 \pmod{m_2}\) - ... - \(x \equiv a_k \pmod{m_k}\)

където \(m_1, m_2, ..., m_k\) са взаимно прости.

long long chineseRemainder(vector<int> num, vector<int> rem) {
    long long prod = 1;
    for (int i = 0; i < num.size(); i++) {
        prod *= num[i];
    }

    long long result = 0;
    for (int i = 0; i < num.size(); i++) {
        long long pp = prod / num[i];
        result += rem[i] * modInverse(pp, num[i]) * pp;
    }

    return result % prod;
}

10. Функция на Ойлер φ(n)

Брой на числата от 1 до n, които са взаимно прости с n.

Формула: \(\phi(n) = n \cdot \prod_{p|n} (1 - \frac{1}{p})\)

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;
}

Приложение: Малка теорема на Ферма обобщена (Теорема на Ойлер): $\(a^{\phi(m)} \equiv 1 \pmod{m}\)$

11. Практически задачи

  1. Намиране на НОД на 3 числа: \(\gcd(a, b, c) = \gcd(a, \gcd(b, c))\)
  2. Перфектно число: Числото е равно на сумата на собствените си делители (напр. 6 = 1 + 2 + 3)
  3. Числа на Армстронг: \(153 = 1^3 + 5^3 + 3^3\)
  4. Решаване на линейни диофантови уравнения: \(ax + by = c\) има решение ⟺ \(\gcd(a,b) | c\)

💡 Важни забележки

  • При работа с големи числа винаги използвайте long long
  • При модулярна аритметика приложете модула след всяка операция
  • НОД и НОК се срещат в много олимпиадни задачи - научете ги наизуст
  • Разширеният алгоритъм на Евклид е ключов за модулярно обратно

🏁 Съвет

Теорията на числата е фундаментална в състезателното програмиране. Всички тези алгоритми са често използвани в задачи от IOI, CEOI, балкански олимпиади и Codeforces. Практикувайте редовно и винаги помнете за edge cases като n=0, n=1 и отрицателни числа!

```