Modint (math/modint.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-05-11 17:00:24+09:00
• Include: #include "math/modint.hpp"

自動で剰余を取ります。

使い方

コンストラクタ

ModInt(const int64_t x = 0)

説明

int64_t 型の整数 x を基に、法 Mod で剰余を取った値を保持する ModInt オブジェクトを構築します。

• x: 初期値。デフォルトは 0 です。

計算量

$O(1)$

演算子

説明

ModInt は以下の算術演算子をオーバーロードしており、すべて法 Mod の下で行われます。

• +: 加算
• -: 減算 (単項および二項)
• *: 乗算
• /: 除算 (逆元を乗算することで実現)
• +=: 加算代入
• -=: 減算代入
• *=: 乗算代入
• /=: 除算代入

計算量

加算、減算、乗算、およびそれらの複合代入演算子 (+=, -=, *=) は $O(1)$ です。 除算 (/, /=) は逆元計算のため $O(\log Mod)$ です。

pow

constexpr ModInt pow(int64_t n) const noexcept

説明

自身の n 乗を計算します。繰り返し二乗法を用いて効率的に計算します。

• n: 冪指数。

制約

$0 \leq n$

計算量

$O(\log n)$

Verified with

• test/unionfind_with_potential.test.cpp

Code

#pragma once
#include <cstdint>

template <int64_t Mod>
struct Modint {
    int64_t x;
    constexpr Modint(const int64_t x = 0) noexcept : x(x % Mod) {}
    constexpr Modint operator+(const Modint rhs) const noexcept {
        return Modint(*this) += rhs;
    }
    constexpr Modint operator-(const Modint rhs) const noexcept {
        return Modint(*this) -= rhs;
    }
    constexpr Modint &operator-() noexcept {
        if (x != 0) {
            x = -x + Mod;
        }
        return *this;
    }
    constexpr Modint operator*(const Modint rhs) const noexcept {
        return Modint(*this) *= rhs;
    }
    constexpr Modint operator/(const Modint rhs) const noexcept {
        return Modint(*this) /= rhs;
    }
    constexpr Modint &operator+=(const Modint rhs) noexcept {
        x += rhs.x;
        if (x >= Mod) {
            x -= Mod;
        }
        return *this;
    }
    constexpr Modint &operator-=(const Modint rhs) noexcept {
        if (x < rhs.x) {
            x += Mod;
        }
        x -= rhs.x;
        return *this;
    }
    constexpr Modint &operator*=(const Modint rhs) noexcept {
        x = (x * rhs.x) % Mod;
        return *this;
    }
    constexpr Modint &operator/=(Modint rhs) noexcept {
        *this *= rhs.pow(Mod - 2);
        return *this;
    }
    constexpr Modint pow(int64_t n) const noexcept {
        Modint a = *this, res = 1;
        while (n) {
            if (n & 1) {
                res *= a;
            }
            a *= a;
            n >>= 1;
        }
        return res;
    }
};

#line 2 "math/modint.hpp"
#include <cstdint>

template <int64_t Mod>
struct Modint {
    int64_t x;
    constexpr Modint(const int64_t x = 0) noexcept : x(x % Mod) {}
    constexpr Modint operator+(const Modint rhs) const noexcept {
        return Modint(*this) += rhs;
    }
    constexpr Modint operator-(const Modint rhs) const noexcept {
        return Modint(*this) -= rhs;
    }
    constexpr Modint &operator-() noexcept {
        if (x != 0) {
            x = -x + Mod;
        }
        return *this;
    }
    constexpr Modint operator*(const Modint rhs) const noexcept {
        return Modint(*this) *= rhs;
    }
    constexpr Modint operator/(const Modint rhs) const noexcept {
        return Modint(*this) /= rhs;
    }
    constexpr Modint &operator+=(const Modint rhs) noexcept {
        x += rhs.x;
        if (x >= Mod) {
            x -= Mod;
        }
        return *this;
    }
    constexpr Modint &operator-=(const Modint rhs) noexcept {
        if (x < rhs.x) {
            x += Mod;
        }
        x -= rhs.x;
        return *this;
    }
    constexpr Modint &operator*=(const Modint rhs) noexcept {
        x = (x * rhs.x) % Mod;
        return *this;
    }
    constexpr Modint &operator/=(Modint rhs) noexcept {
        *this *= rhs.pow(Mod - 2);
        return *this;
    }
    constexpr Modint pow(int64_t n) const noexcept {
        Modint a = *this, res = 1;
        while (n) {
            if (n & 1) {
                res *= a;
            }
            a *= a;
            n >>= 1;
        }
        return res;
    }
};

Back to top page