guest@itl:~/home/number-theory$
templates/modint.cpp
compilable
$cat templates/modint

Modular Integer (ModInt)

Type-safe modular arithmetic with operator overloading for clean competitive programming code.

[Number Theory]|
Jul 9, 2026
|explanatory_notes.md|
#modint#modular#arithmetic#operator-overloading
Log in to track progress, save custom versions, and organize into collections.Log In
$cat source_code/
cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

template <int MOD = 1000000007>
struct ModInt {
    int val;

    ModInt(ll v = 0) { val = v % MOD; if (val < 0) val += MOD; }

    ModInt operator+(const ModInt &o) const { return ModInt(val + o.val); }
    ModInt operator-(const ModInt &o) const { return ModInt(val - o.val); }
    ModInt operator*(const ModInt &o) const { return ModInt((ll)val * o.val); }
    ModInt operator/(const ModInt &o) const { return *this * o.inv(); }

    ModInt &operator+=(const ModInt &o) { val = (val + o.val) % MOD; return *this; }
    ModInt &operator-=(const ModInt &o) { val = (val - o.val + MOD) % MOD; return *this; }
    ModInt &operator*=(const ModInt &o) { val = (ll)val * o.val % MOD; return *this; }
    ModInt &operator/=(const ModInt &o) { return *this = *this / o; }

    ModInt pow(ll e) const {
        ModInt res(1), b(val);
        while (e > 0) {
            if (e & 1) res *= b;
            b *= b;
            e >>= 1;
        }
        return res;
    }

    ModInt inv() const { return pow(MOD - 2); }

    bool operator==(const ModInt &o) const { return val == o.val; }
    bool operator!=(const ModInt &o) const { return val != o.val; }
    friend ostream &operator<<(ostream &os, const ModInt &m) { return os << m.val; }
    friend istream &operator>>(istream &is, ModInt &m) { ll v; is >> v; m = ModInt(v); return is; }
};
37 linesutf-8
$cat explanation_notes.md
notes_viewer --renderedmarkdown (math enabled)

ModInt

A wrapper type that automatically applies  mod M\bmod M after every operation. Eliminates the most common source of bugs in CP: forgetting % MOD at intermediate steps.

Operations

  • Arithmetic — +, -, *, / all work naturally between ModInt values

  • Power — pow(e) computes ae mod Ma^e \bmod M via binary exponentiation

  • Inverse — inv() computes a−1≡aM−2(modM)a^{-1} \equiv a^{M-2} \pmod{M} (Fermat's little theorem, requires prime MM)

  • I/O — cout << x prints the value directly

    • When to Use

  • Any problem with "answer modulo 109+710^9 + 7" or "modulo 998244353998244353"

  • Combinatorics, DP, counting problems where every operation needs mod

  • When you want code that reads like textbook math instead of % MOD everywhere

    • Notes

  • The template parameter MOD must be prime for division/inverse to work

  • Change MOD by using: using Mint = ModInt<998244353>;

  • Constructor handles negative values correctly

    • Complexity

  • +, -, * — O(1)O(1)

  • /, inv() — O(log⁡M)O(\log M)

  • pow(e) — O(log⁡e)O(\log e)