Algoritmi → Matematički algoritmi → Teorija brojeva za takmičenja

Teorija brojeva za takmičenja

Deljivost i ostaci

Broj a je deljiv sa b ako je a % b == 0. Ostatak pri deljenju je osnova mnogih zadataka: cifre broja (% 10), parnost (% 2), ciklusi (dan u nedelji je % 7). Pazi: u C++-u je ostatak negativnog broja negativan (-7 % 3 == -1), pa se za matematički ostatak piše ((a % m) + m) % m.

Prosti brojevi

• Provera da li je broj prost: deljenje do √n – Prosti brojevi i faktorizacija.
• Svi prosti brojevi do 10⁷: Eratostenovo sito, složenost O(n log log n).
• Rastavljanje na proste činioce i broj delilaca: ako je n = p₁^a₁ · … · pₖ^aₖ, broj delilaca je (a₁+1)·…·(aₖ+1).

NZD i NZS

Euklidov algoritam: nzd(a, b) = nzd(b, a % b), složenost O(log min(a, b)). NZS je a / nzd(a, b) * b. U C++17 postoje gotove funkcije gcd i lcm (zaglavlje <numeric>). Detaljno: Određivanje NZD i NZS.

Modularna aritmetika

Kada je tačan rezultat ogroman (broj puteva, broj rasporeda…), zadatak traži ostatak pri deljenju nekim brojem m, najčešće 109 + 7 (prost broj). Važe pravila:

• (a + b) mod m = ((a mod m) + (b mod m)) mod m
• (a − b) mod m = ((a mod m) − (b mod m) + m) mod m
• (a · b) mod m = ((a mod m) · (b mod m)) mod m

Zato se ostatak uzima posle svake operacije, pa međurezultati ostaju mali. Proizvod dva broja manja od 10⁹+7 je manji od 10¹⁸ i staje u long long.

Deljenje ne radi po istom pravilu. Umesto deljenja sa a množi se modularnim inverzom a⁻¹ – brojem za koji je a · a⁻¹ mod m = 1. Kada je m prost i a nije deljiv sa m, po maloj Fermaovoj teoremi a⁻¹ = am−2 mod m.

#include <iostream>
using namespace std;

const long long MOD = 1000000007;

long long stepen(long long a, long long b) {      // a^b mod MOD
    long long r = 1;
    a %= MOD;
    while (b > 0) {
        if (b & 1) r = r * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return r;
}

long long inverz(long long a) { return stepen(a, MOD - 2); }

int main() {
    long long a, b;
    cin >> a >> b;
    cout << (a + b) % MOD << "\n";
    cout << ((a - b) % MOD + MOD) % MOD << "\n";      // nikad negativno
    cout << a % MOD * (b % MOD) % MOD << "\n";
    cout << a % MOD * inverz(b) % MOD << "\n";        // "a / b" po modulu
    return 0;
}

Poslednji red za a = 10, b = 4 daje 500000006 – to je broj x za koji je 4 · x ≡ 10 (mod 109+7), tj. „10/4 = 2,5“ po modulu.

Brzo stepenovanje

ab mod m za b do 10¹⁸ računa se u O(log b) koraka, polovljenjem izložioca (funkcija stepen iznad). Objašnjenje korak po korak: Algoritam brzog stepenovanja, a rekurzivna verzija u lekciji Faktorijel, stepen i NZD – rekurzivno.

Šta dalje

• Kombinatorika – faktorijeli i kombinacije po modulu.
• Zamena iteracija formulom – kako petlju zameniti matematičkom formulom.
• Algoritmi – primeri – zadaci sa NZD-om, prostim brojevima i deljivošću.

Zadaci za vežbu

Za svaki zadatak postoji primer, uputstvo i rešenje. Rešenja su provereno tačna na primerima iz teksta.

Proveri znanje