Modint構造体
(algorithm/Math/ModularArithmetic/modint.hpp)

• View this file on GitHub
• Last update: 2025-07-03 00:41:25+09:00
• Include: #include "algorithm/Math/ModularArithmetic/modint.hpp"

概要

任意の自然数 $m \geq 1$ を法として，四則演算時に剰余をとる構造体．

自然数 $m$ を法とする剰余類の代表元（$0$ 以上 $m$ 未満）を値として保存し，剰余類環 $\mathbb{Z}/m\mathbb{Z}$ における加法と乗法の演算をサポートする．

\[\begin{align} &a + m \mathbb{Z}, \ b + m \mathbb{Z} \in \mathbb{Z} / m \mathbb{Z}, \notag\\ &(a + m \mathbb{Z}) + (b + m \mathbb{Z}) = (a + b) + m \mathbb{Z}, \notag\\ &(a + m \mathbb{Z})(b + m \mathbb{Z}) = a b + m \mathbb{Z} \notag\\ \end{align}\]

また，任意の素数 $p$ を法としたときは，剰余体 $\mathbb{Z}/p\mathbb{Z}$ において $0+p\mathbb{Z}$ 以外の剰余類 $a+p\mathbb{Z} \in \mathbb{Z}/p\mathbb{Z}$ は乗法逆元 $a^{-1}$ をもち，除法の演算もサポートする．

\[\frac{b + m \mathbb{Z}}{a + m \mathbb{Z}} = b \cdot a^{-1} + m \mathbb{Z}\]

参考文献

1. “剰余類環”. Wikipedia. https://ja.wikipedia.org/wiki/剰余類環.
2. “モジュラ逆数”. Wikipedia. https://ja.wikipedia.org/wiki/モジュラ逆数.
3. drken. “「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜”. Qiita. https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a.
4. “群・環・体”. HatenaBlog. https://zellij.hatenablog.com/entry/20121211/p1.

Depends on

• Modint構造体の基底クラス (algorithm/Math/ModularArithmetic/modint_base.hpp)

Verified with

• verify/yosupo-convolution_mod-number_theoretic_transform.test.cpp
• verify/yosupo-point_set_range_composite-segment_tree.test.cpp
• verify/yosupo-range_affine_range_sum-lazy_segment_tree.test.cpp

Code

#ifndef ALGORITHM_MODINT_HPP
#define ALGORITHM_MODINT_HPP 1

#include <iostream>
#include <utility>

#include "modint_base.hpp"

namespace algorithm {

template <int mod>
class Modint : ModintBase {
    static_assert(mod >= 1);

    long long val;

    constexpr void normalize() {
        if(val < -mod or mod <= val) val %= mod;
        if(val < 0) val += mod;
    }

public:
    constexpr Modint() : val(0) {}
    constexpr Modint(long long val) : val(val) {
        normalize();
    }

    constexpr Modint operator+() const { return Modint(*this); }
    constexpr Modint operator-() const {
        if(val == 0) Modint();
        Modint res = *this;
        res.val = mod - res.val;
        return res;
    }
    constexpr Modint &operator++() {
        val++;
        if(val == mod) val = 0;
        return *this;
    }
    constexpr Modint &operator--() {
        if(val == 0) val = mod;
        val--;
        return *this;
    }
    constexpr Modint operator++(int) {
        Modint res = *this;
        ++(*this);
        return res;
    }
    constexpr Modint operator--(int) {
        Modint res = *this;
        --(*this);
        return res;
    }
    constexpr Modint &operator+=(const Modint &rhs) {
        val += rhs.val;
        if(val >= mod) val -= mod;
        return *this;
    }
    constexpr Modint &operator-=(const Modint &rhs) {
        val -= rhs.val;
        if(val < 0) val += mod;
        return *this;
    }
    constexpr Modint &operator*=(const Modint &rhs) {
        val = val * rhs.val % mod;
        return *this;
    }
    constexpr Modint &operator/=(const Modint &rhs) { return *this *= rhs.inv(); }

    friend constexpr bool operator==(const Modint &lhs, const Modint &rhs) { return lhs.val == rhs.val; }
    friend constexpr Modint operator+(const Modint &lhs, const Modint &rhs) { return Modint(lhs) += rhs; }
    friend constexpr Modint operator-(const Modint &lhs, const Modint &rhs) { return Modint(lhs) -= rhs; }
    friend constexpr Modint operator*(const Modint &lhs, const Modint &rhs) { return Modint(lhs) *= rhs; }
    friend constexpr Modint operator/(const Modint &lhs, const Modint &rhs) { return Modint(lhs) /= rhs; }
    friend std::istream &operator>>(std::istream &is, Modint &rhs) {
        is >> rhs.val;
        rhs.normalize();
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Modint &rhs) { return os << rhs.val; }

    static constexpr int modulus() { return mod; }
    constexpr long long value() const { return val; }
    constexpr Modint inv() const {
        long long a = mod, b = val, u = 0, v = 1;
        while(b != 0) {
            long long t = a / b;
            a -= b * t, u -= v * t;
            std::swap(a, b), std::swap(u, v);
        }
        return Modint(u);
    }
    constexpr Modint pow(long long k) const {
        if(k < 0) return inv().pow(-k);
        Modint res = 1, mul = *this;
        while(k > 0) {
            if(k & 1LL) res *= mul;
            mul *= mul;
            k >>= 1;
        }
        return res;
    }

    friend constexpr Modint mod_inv(const Modint &a) { return a.inv(); }
    friend constexpr Modint mod_pow(const Modint &a, long long k) { return a.pow(k); }
};

using mint998244353 = Modint<998'244'353>;
using mint1000000007 = Modint<1'000'000'007>;

}  // namespace algorithm

#endif

#line 1 "algorithm/Math/ModularArithmetic/modint.hpp"



#include <iostream>
#include <utility>

#line 1 "algorithm/Math/ModularArithmetic/modint_base.hpp"



#include <type_traits>

namespace algorithm {

class ModintBase {};

template <class T>
using is_modint = std::is_base_of<ModintBase, T>;

template <class T>
inline constexpr bool is_modint_v = is_modint<T>::value;

}  // namespace algorithm


#line 8 "algorithm/Math/ModularArithmetic/modint.hpp"

namespace algorithm {

template <int mod>
class Modint : ModintBase {
    static_assert(mod >= 1);

    long long val;

    constexpr void normalize() {
        if(val < -mod or mod <= val) val %= mod;
        if(val < 0) val += mod;
    }

public:
    constexpr Modint() : val(0) {}
    constexpr Modint(long long val) : val(val) {
        normalize();
    }

    constexpr Modint operator+() const { return Modint(*this); }
    constexpr Modint operator-() const {
        if(val == 0) Modint();
        Modint res = *this;
        res.val = mod - res.val;
        return res;
    }
    constexpr Modint &operator++() {
        val++;
        if(val == mod) val = 0;
        return *this;
    }
    constexpr Modint &operator--() {
        if(val == 0) val = mod;
        val--;
        return *this;
    }
    constexpr Modint operator++(int) {
        Modint res = *this;
        ++(*this);
        return res;
    }
    constexpr Modint operator--(int) {
        Modint res = *this;
        --(*this);
        return res;
    }
    constexpr Modint &operator+=(const Modint &rhs) {
        val += rhs.val;
        if(val >= mod) val -= mod;
        return *this;
    }
    constexpr Modint &operator-=(const Modint &rhs) {
        val -= rhs.val;
        if(val < 0) val += mod;
        return *this;
    }
    constexpr Modint &operator*=(const Modint &rhs) {
        val = val * rhs.val % mod;
        return *this;
    }
    constexpr Modint &operator/=(const Modint &rhs) { return *this *= rhs.inv(); }

    friend constexpr bool operator==(const Modint &lhs, const Modint &rhs) { return lhs.val == rhs.val; }
    friend constexpr Modint operator+(const Modint &lhs, const Modint &rhs) { return Modint(lhs) += rhs; }
    friend constexpr Modint operator-(const Modint &lhs, const Modint &rhs) { return Modint(lhs) -= rhs; }
    friend constexpr Modint operator*(const Modint &lhs, const Modint &rhs) { return Modint(lhs) *= rhs; }
    friend constexpr Modint operator/(const Modint &lhs, const Modint &rhs) { return Modint(lhs) /= rhs; }
    friend std::istream &operator>>(std::istream &is, Modint &rhs) {
        is >> rhs.val;
        rhs.normalize();
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Modint &rhs) { return os << rhs.val; }

    static constexpr int modulus() { return mod; }
    constexpr long long value() const { return val; }
    constexpr Modint inv() const {
        long long a = mod, b = val, u = 0, v = 1;
        while(b != 0) {
            long long t = a / b;
            a -= b * t, u -= v * t;
            std::swap(a, b), std::swap(u, v);
        }
        return Modint(u);
    }
    constexpr Modint pow(long long k) const {
        if(k < 0) return inv().pow(-k);
        Modint res = 1, mul = *this;
        while(k > 0) {
            if(k & 1LL) res *= mul;
            mul *= mul;
            k >>= 1;
        }
        return res;
    }

    friend constexpr Modint mod_inv(const Modint &a) { return a.inv(); }
    friend constexpr Modint mod_pow(const Modint &a, long long k) { return a.pow(k); }
};

using mint998244353 = Modint<998'244'353>;
using mint1000000007 = Modint<1'000'000'007>;

}  // namespace algorithm

Back to top page