Skip to main content

​
Overview

Numeric utilities for competitive programming including modular arithmetic with automatic operations, fast exponentiation, and arbitrary precision integers.

​
Modular Integer (Mint)

A template class for modular arithmetic that handles all operations automatically.

​
Basic Mint

template<typename Type>
struct Modular {
    using T = typename decay<decltype(Type::value)>::type;
    T value;
    
    Modular();
    Modular(int64_t num);
    
    Modular& operator+=(const Modular& m);
    Modular& operator-=(const Modular& m);
    Modular& operator*=(const Modular& m);
    Modular& operator/=(const Modular& m);
    
    friend Modular operator+(Modular a, const Modular& b);
    friend Modular operator-(Modular a, const Modular& b);
    friend Modular operator*(Modular a, const Modular& b);
    friend Modular operator/(Modular a, const Modular& b);
    
    Modular operator-() const;
    Modular& operator++();
    Modular& operator--();
};

const int MOD = 1e9 + 7;
using Mint = Modular<integral_constant<decay<decltype(MOD)>::type, MOD>>;

​
Modular Inverse

template<typename T>
T inverse(T a, T m);

template<typename Type>
Modular<Type> inverse(const Modular<Type>& a);
Complexity: O(log m) Usage Example: 
const int MOD = 1e9 + 7;
using Mint = Modular<integral_constant<int, MOD>>;

Mint a = 5;
Mint b = 3;
Mint c = a + b;    // 8
Mint d = a * b;    // 15
Mint e = a / b;    // 5 * inverse(3) mod MOD

cout << c << endl;  // Automatically applies modulo

​
Features

​
operator+
Modular operator+(Modular a, const Modular& b)
Modular addition
​
operator*
Modular operator*(Modular a, const Modular& b)
Modular multiplication
​
operator/
Modular operator/(Modular a, const Modular& b)
Modular division (automatically computes inverse)
​
inverse
Modular inverse(const Modular& a)
Compute modular multiplicative inverse

​
Compile-time vs Runtime Modulo

Compile-time (recommended): 
const int MOD = 1e9 + 7;
using Mint = Modular<integral_constant<int, MOD>>;
Runtime (variable modulo): 
using ModType = int;
struct VarMod { static ModType value; };
ModType VarMod::value;
ModType& MOD = VarMod::value;
using Mint = Modular<VarMod>;

// Set modulo at runtime
MOD = 998244353;

​
Versions Available

VersionFileDescription
Compressnumeric_mint_compress.cppMinimal implementation
Mediumnumeric_mint_medium.cppBalanced features
Fullnumeric_mint_full.cppAll features included

​
Fast Power

Computes a^b efficiently using binary exponentiation. 
template<typename T, typename U>
T fastpow(T a, U b);
​
a
T
Base (can be int, Mint, Matrix, etc.)
​
b
U
Exponent (must be non-negative)
Complexity: O(log b) Usage Example: 
// Integer power
int result = fastpow(2, 10);  // 1024

// Modular power
Mint a = 2;
Mint result = fastpow(a, 1000000000);

// Matrix power
Matrix<int> mat(n, n);
Matrix<int> result = fastpow(mat, k);

​
Modular Operations

​
Basic Modular Operations

template<typename T>
T mod(T a, T m);  // Always returns positive result

template<typename T>
T add_mod(T a, T b, T m);

template<typename T>
T sub_mod(T a, T b, T m);

template<typename T>
T mul_mod(T a, T b, T m);

template<typename T>
T pow_mod(T a, T b, T m);
Usage Example: 
const int MOD = 1e9 + 7;
int result = mul_mod(123456789, 987654321, MOD);

​
Fast Modular Operations

Optimized versions for specific moduli. 
template<typename T>
T fast_mul_mod(T a, T b, T m);  // Using __int128

​
BigInt (Arbitrary Precision)

Supports arithmetic with arbitrarily large integers. 
class BigInt {
public:
    BigInt();
    BigInt(long long value);
    BigInt(const string &s);
    
    BigInt operator+(const BigInt &other) const;
    BigInt operator-(const BigInt &other) const;
    BigInt operator*(const BigInt &other) const;
    BigInt operator/(const BigInt &other) const;
    BigInt operator%(const BigInt &other) const;
    
    bool operator<(const BigInt &other) const;
    bool operator==(const BigInt &other) const;
    
    string toString() const;
};
Usage Example: 
BigInt a("123456789012345678901234567890");
BigInt b("987654321098765432109876543210");
BigInt sum = a + b;
BigInt product = a * b;
cout << sum.toString() << endl;
Complexity:
  • Addition/Subtraction: O(n)
  • Multiplication: O(n²) or O(n log n) with FFT
  • Division: O(n²)

​
Common Modular Values

// Common moduli in competitive programming
const int MOD1 = 1e9 + 7;      // 1000000007 (prime)
const int MOD2 = 998244353;     // (prime, NTT-friendly)
const int MOD3 = 1e9 + 9;       // 1000000009 (prime)

​
Advanced Usage

​
Checking Division by Zero

bool is_zero_division(Mint &a) {
    using T = Mint::T;
    return inverse(static_cast<T>(a), MOD) < static_cast<T>(0);
}

​
Using with Combinatorics

Factorial<Mint> fact(1e6);

Mint nCr(int n, int r) {
    if (r < 0 || r > n) return Mint(0);
    return fact[n] / (fact[r] * fact[n-r]);
}

Mint result = nCr(100, 50);

​
Fast Power with Mint

Mint result = fastpow(Mint(2), 1000000000);
// Computes 2^1000000000 mod MOD efficiently

​
Performance Tips

Use Compile-time MOD

Compile-time modulo is faster than runtime

Precompute Factorials

For multiple nCr queries, precompute factorials

Fast Power

Use fastpow for exponentiation, not repeated multiplication

Avoid Division

Modular division is expensive, minimize usage

​
Available Implementations

FeatureFileNotes
Mint (Compress)numeric_mint_compress.cppMinimal, fast
Mint (Medium)numeric_mint_medium.cppGood balance
Mint (Full)numeric_mint_full.cppAll features
Fast Powernumeric_fastpow.cppBinary exponentiation
Modular Opsnumeric_mod.cppBasic operations
Fast Modnumeric_mod_fast.cppOptimized
BigIntnumeric_bigint.cppArbitrary precision

​
See Also

Math Algorithms

GCD, primes, and number theory

Combinatorics

Use Mint with combinatorial functions

Build docs developers (and LLMs) love

Get started for freeTalk to us