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

Основные арифметические операции

• (A + B) % MOD = (A % MOD + B % MOD) % MOD
• (A - B) % MOD = ((A % MOD - B % MOD) % MOD + MOD) % MOD
• (A * B) % MOD = ((A % MOD) * (B % MOD)) % MOD

«Деление» и нахождение обратного элемента

• (A / B) % MOD = ((A % MOD) * B^-1) % MOD

• Если MOD простой: B^-1 = B^{MOD - 2} % MOD
• Если B и MOD взаимно просты: B^-1 = X, где gcdex(B % MOD, MOD, X, Y) == 1
• Если B и MOD не взаимно просты, решения не существует.

class ModInt {
    long long value;
    static const long long mod = 1e9 + 7;

    static long long gcdex(long long a, long long b, long long &x, long long &y) {
        if (!b) {
            x = 1;
            y = 0;
            return a;
        }
        long long x1, y1, d = gcdex(b, a % b, x1, y1);
        x = y1;
        y = x1 - a / b * y1;
        return d;
    }

public:
    ModInt(long long value = 0) : value((value % mod + mod) % mod) {}

    ModInt operator + (const ModInt &that) const {
        return value + that.value;
    }

    ModInt operator - (const ModInt &that) const {
        return value - that.value;
    }

    ModInt operator * (const ModInt &that) const {
        return value * that.value;
    }

    ModInt operator / (const ModInt &that) const {
        long long x, y;
        gcdex(that.value, mod, x, y);
        return value * x;
    }

    bool canDivide(const ModInt &that) const {
        long long x, y;
        return that.value && gcdex(that.value, mod, x, y) == 1;
    }

    friend istream &operator >> (istream &in, ModInt &m) {
        long long value;
        in >> value;
        m = ModInt(value);
        return in;
    }

    friend ostream &operator << (ostream &out, const ModInt &m) {
        return out << m.value;
    }
};

Ссылки

Теория:

• e-maxx.ru — Обратный элемент в кольце по модулю
• cp-algorithms.com — Modular Inverse
• brestprog.by — Операции по модулю
• algorithmica.org — Модульная арифметика, обратный элемент: 1 2 3 4
• usaco.guide — Modular Arithmetics
• codeforces.com — Modular Arithmetic for Beginners

Код:

• indy256/codelibrary/cpp/numbertheory/modint.h