guest@cp-base:~/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
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#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)