kz-maxx

RU KZ
← Басты бет

Модульная арифметика

Қалдықтар, mod, қосу, азайту, көбейту, дәреже, inverse және mod бойынша бөлу

Модуль деген не?

Модуль — бұл бөлгендегі қалдық.

Мысалы: 

17 mod 5 = 2

Себебі: 

17 = 5 * 3 + 2

C++ тілінде қалдық алу операторы: 

%

C++ мысалы

int a = 17;
int m = 5;

cout << a % m;

Output: 

2
Олимпиадалық задачаларда answer-ды көбіне mod бойынша шығар дейді. Мысалы, 1e9 + 7 бойынша.

mod не үшін керек?

Кейбір задачада answer өте үлкен болуы мүмкін. Мысалы, тәсілдер саны өте үлкен сан болады. Сондықтан толық answer емес, оның mod бойынша қалдығын шығарамыз.

answer өте үлкен болуы мүмкін
бірақ біз answer % MOD шығарамыз

Ең популярный MOD: 

const long long MOD = 1000000007;

Модуль бойынша теңдік

Екі сан m модулі бойынша тең болады, егер оларды m-ге бөлгенде қалдықтары бірдей болса. 

17 mod 5 = 2
7 mod 5 = 2

Сондықтан: 

17 ≡ 7 (mod 5)

Бұл былай оқылады: 17 саны 7 санына 5 модулі бойынша тең.

Модуль бойынша қосу

Екі санды қосып, mod алу керек болса: 

(a + b) % MOD

Мысал: 

a = 8
b = 9
MOD = 10

(8 + 9) % 10 = 17 % 10 = 7

Модуль бойынша азайту

Азайтқанда теріс сан шығуы мүмкін.

Мысалы: 

3 - 7 = -4

Сондықтан қауіпсіз формула: 

(a - b + MOD) % MOD

Егер сандар өте үлкен немесе теріс болуы мүмкін болса: 

((a - b) % MOD + MOD) % MOD

Модуль бойынша көбейту

Көбейту үшін: 

(a * b) % MOD

Бірақ a және b үлкен болса, overflow болуы мүмкін. Сондықтан көбіне long long қолданамыз. 

long long res = a * b % MOD;

Базалық функциялар

const long long MOD = 1000000007;

long long add(long long a, long long b) {
    return (a + b) % MOD;
}

long long sub(long long a, long long b) {
    return (a - b + MOD) % MOD;
}

long long mul(long long a, long long b) {
    return a * b % MOD;
}

Санды нормализация жасау

Кейде сан теріс болуы мүмкін. Оны 0-ден MOD - 1-ге дейінгі дұрыс қалдыққа келтіру керек. 

long long norm(long long x) {
    x %= MOD;

    if (x < 0) {
        x += MOD;
    }

    return x;
}

Мысал: 

-1 mod 5 = 4

Базалық операциялардың толық коды

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1000000007;

long long norm(long long x) {
    x %= MOD;

    if (x < 0) {
        x += MOD;
    }

    return x;
}

long long add(long long a, long long b) {
    return norm(a + b);
}

long long sub(long long a, long long b) {
    return norm(a - b);
}

long long mul(long long a, long long b) {
    return norm(a) * norm(b) % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long a, b;
    cin >> a >> b;

    cout << add(a, b) << '\n';
    cout << sub(a, b) << '\n';
    cout << mul(a, b) << '\n';

    return 0;
}

Модуль бойынша дәреже

Көбіне тез есептеу керек болады: 

a^b mod MOD

Егер b үлкен болса, a-ны b рет көбейтуге болмайды.

Сондықтан быстрое возведение в степень қолданамыз.

егер b жұп болса: a^b = (a^(b/2))²
егер b тақ болса: a^b = a * a^(b-1)

Быстрая степень идеясы

O(b) операция орнына O(log b) операция жасаймыз.

Мысалы: 

2^10 = 1024

Бірақ біз 10 рет бірінен кейін бірін көбейтпейміз. Степеньті екіге бөліп отырамыз.

Бұл number theory ішіндегі ең маңызды шаблондардың бірі.

Быстрая степень коды

long long binpow(long long a, long long b) {
    long long res = 1;

    a %= MOD;

    while (b > 0) {
        if (b % 2 == 1) {
            res = res * a % MOD;
        }

        a = a * a % MOD;
        b /= 2;
    }

    return res;
}

Дәреженің толық реализациясы

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1000000007;

long long binpow(long long a, long long b) {
    long long res = 1;

    a %= MOD;

    while (b > 0) {
        if (b % 2 == 1) {
            res = res * a % MOD;
        }

        a = a * a % MOD;
        b /= 2;
    }

    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long a, b;
    cin >> a >> b;

    cout << binpow(a, b);

    return 0;
}

Input / Output

Input

2 10

Output

1024

Неге жай бөлуге болмайды?

Обычный арифметикада: 

10 / 2 = 5

Бірақ mod бойынша былай жазуға болмайды: 

a / b % MOD

Себебі mod арифметикада бөлу обратный элемент арқылы жасалады.

Модульная арифметикада бөлу = inverse-ке көбейту.

Обратный элемент деген не?

x саны a санының MOD бойынша обратный элементі болады, егер: 

a * x ≡ 1 (mod MOD)

Онда: 

a / b mod MOD = a * inverse(b) mod MOD

Обратный элемент қашан бар?

a санының m модулі бойынша inverse-і бар, егер: 

gcd(a, m) = 1

Яғни a және m өзара жай болуы керек.

Егер MOD жай сан болса, онда 1-ден MOD - 1-ге дейінгі кез келген санның inverse-і бар.

Обратный элемент Ферма теоремасы арқылы

Егер MOD жай сан болса: 

inverse(a) = a^(MOD - 2) mod MOD

Сондықтан binpow қолданамыз: 

long long inv(long long a) {
    return binpow(a, MOD - 2);
}
Бұл тек MOD жай сан болса және a MOD-қа бөлінбесе ғана жұмыс істейді.

Модуль бойынша бөлу

Есептеу керек: 

a / b mod MOD

Жазамыз: 

a * inv(b) % MOD

Код: 

long long divide(long long a, long long b) {
    return a % MOD * inv(b) % MOD;
}

Толық код: mod бойынша бөлу

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1000000007;

long long binpow(long long a, long long b) {
    long long res = 1;

    a %= MOD;

    while (b > 0) {
        if (b % 2 == 1) {
            res = res * a % MOD;
        }

        a = a * a % MOD;
        b /= 2;
    }

    return res;
}

long long inv(long long a) {
    return binpow(a, MOD - 2);
}

long long divide_mod(long long a, long long b) {
    return a % MOD * inv(b) % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long a, b;
    cin >> a >> b;

    cout << divide_mod(a, b);

    return 0;
}

Inverse мысалы

Болсын: 

MOD = 7
a = 3

Бізге сондай x табу керек: 

3 * x ≡ 1 (mod 7)

Тексерейік: 

3 * 5 = 15
15 mod 7 = 1

Демек: 

inverse(3) = 5

Inverse extended Euclid арқылы

Егер mod жай сан болуы міндетті емес болса, extended Euclid қолдануға болады.

Ол табады: 

a * x + m * y = gcd(a, m)

Егер gcd(a, m) = 1, онда: 

a * x ≡ 1 (mod m)

Демек x — inverse.

inverse extended gcd арқылы код

long long extgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }

    long long x1, y1;
    long long d = extgcd(b, a % b, x1, y1);

    x = y1;
    y = x1 - (a / b) * y1;

    return d;
}

long long inv_general(long long a, long long m) {
    long long x, y;
    long long d = extgcd(a, m, x, y);

    if (d != 1) {
        return -1;
    }

    x %= m;

    if (x < 0) {
        x += m;
    }

    return x;
}
Егер функция -1 қайтарса, inverse жоқ деген сөз.

Комбинаторика mod бойынша

Көбіне есептеу керек: 

C(n, k) mod MOD

Формула: 

C(n, k) = n! / (k! * (n-k)!)

Mod бойынша бөлу inverse арқылы жасалады.

Факториал және inverse factorial

fact[i] = i!
invFact[i] = inverse(i!)

Сонда: 

C(n, k) = fact[n] * invFact[k] % MOD * invFact[n - k] % MOD

C(n, k) mod бойынша код

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1000000007;
const int N = 1000000;

long long fact[N + 1];
long long invFact[N + 1];

long long binpow(long long a, long long b) {
    long long res = 1;

    while (b > 0) {
        if (b % 2 == 1) {
            res = res * a % MOD;
        }

        a = a * a % MOD;
        b /= 2;
    }

    return res;
}

long long inv(long long a) {
    return binpow(a, MOD - 2);
}

void build() {
    fact[0] = 1;

    for (int i = 1; i <= N; i++) {
        fact[i] = fact[i - 1] * i % MOD;
    }

    invFact[N] = inv(fact[N]);

    for (int i = N - 1; i >= 0; i--) {
        invFact[i] = invFact[i + 1] * (i + 1) % MOD;
    }
}

long long C(int n, int k) {
    if (k < 0 || k > n) {
        return 0;
    }

    return fact[n] * invFact[k] % MOD * invFact[n - k] % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    build();

    int n, k;
    cin >> n >> k;

    cout << C(n, k);

    return 0;
}

Overflow болмайтын mod көбейту

Егер сандар 10¹⁸-ге дейін болса, long long * long long та overflow беруі мүмкін.

C++ ішінде __int128 қолдануға болады: 

long long mul_mod(long long a, long long b, long long mod) {
    return (__int128)a * b % mod;
}
Бұл үлкен сандар және Miller-Rabin сияқты задачаларда пайдалы.

Типтік қателер

  • Обычный бөлу a / b жазу, ал керек a * inv(b)
  • Көбейтуден кейін mod алмау
  • Азайтудан кейін теріс қалдық алу
  • gcd(b, MOD) != 1 болса да inverse қолдану
  • MOD жай сан емес кезде Ферма формуласын қолдану
  • a * b ішінде overflow алу
  • 0 санының inverse-і жоқ екенін ұмыту

Асимптотика

Операция Уақыт
Mod бойынша қосу O(1)
Mod бойынша азайту O(1)
Mod бойынша көбейту O(1)
Быстрая степень O(log b)
Inverse Ферма арқылы O(log MOD)
C(n, k) build кейін O(1)

Қашан не қолданамыз?

қосу керек → (a + b) % MOD
азайту керек → (a - b + MOD) % MOD
көбейту керек → a * b % MOD
дәреже керек → binpow(a, b)
бөлу керек → a * inv(b) % MOD
C(n,k) керек → factorial + inverse factorial

Қысқа шаблон

const long long MOD = 1000000007;

long long norm(long long x) {
    x %= MOD;

    if (x < 0) {
        x += MOD;
    }

    return x;
}

long long binpow(long long a, long long b) {
    long long res = 1;

    a = norm(a);

    while (b > 0) {
        if (b % 2 == 1) {
            res = res * a % MOD;
        }

        a = a * a % MOD;
        b /= 2;
    }

    return res;
}

long long inv(long long a) {
    return binpow(a, MOD - 2);
}