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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску

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

  • (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 = BMOD - 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;
    }
};

Ссылки

Теория:

Код: