ModInt 構造体
(Mathematics/ModInt.hpp)

• View this file on GitHub
• Last update: 2021-06-05 13:56:14+09:00
• Include: #include "Mathematics/ModInt.hpp"
• Link: https://tkmst201.github.io/Library/Mathematics/ModInt.hpp

概要

自動で mod を取ってくれる構造体です。 基本的な四則演算や std::cin、std::cout に対応しています。
int が渡せるほとんどのライブラリで用いることができます。

• ModInt(long long val = 0)
  • $\Theta(1)$ $val$ で初期化
• static int mod()
  • $\Theta(1)$ $M$ を返す
• int val()
  • $\Theta(1)$ $x \bmod{M}$ を返す
• ModInt pow(long long n)
  • $\Theta(\log{n})\ (n \geq 0),\ \Theta(\log{n} + \log{M})\ (n < 0)$ $x^n \bmod{M}$ を返す
• ModInt inv()
  • $\Theta(\log{M})$ $x^{-1} \bmod{M}$ を返す

コンストラクタ

mod に取りたい値を $M$ に渡します。

制約

• $M > 0$

---

ModInt(long long val = 0)

$val \bmod{M}$ で初期化します。 何も指定しない場合の初期値は $0$ です。

計算量

• $\Theta(1)$

---

演算

以下の演算が使用可能です。

+ModInt
-ModInt

ModInt++
ModInt--

++ModInt
--ModInt

ModInt += ModInt
ModInt -= ModInt
ModInt *= ModInt
ModInt /= ModInt

ModInt + ModInt
ModInt - ModInt
ModInt * ModInt
ModInt / ModInt

bool(ModInt)
!ModInt
ModInt == ModInt
ModInt != ModInt

std::cin >> ModInt
std::cout << ModInt

bool(ModInt) は法 $M$ で $0$ なら $true$ を、$0$ 以外なら $false$ を返します。 !ModInt は bool(ModInt) を論理否定した値を返します
ModInt == ModInt は 2 つの ModInt の値が法 $M$ の元で合同ならば $true$ を、違えば $false$ を返します。 ModInt != ModInt はその逆の論理値になります。

また、int + ModInt や ModInt + int などの他の型との演算は、それぞれ ModInt(int) + ModInt 、 ModInt + ModInt(int) として計算します。

制約

• ModInt /= ModInt または ModInt / ModInt のとき、右辺の値と $M$ は互いに素

計算量

• $\Theta(\log{M})$ ( ModInt /= ModInt または ModInt / ModInt )
• $\Theta(1)$ (それ以外)

メンバ関数

以下、保持している値を $x$ とします。

---

static int mod()

$M$ を返します。

計算量

• $\Theta(1)$

---

int val()

$x \bmod{M}$ を返します。

計算量

• $\Theta(1)$

---

ModInt pow(long long n)

$x^n \bmod{M}$ を返します。

制約

• $n < 0$ のとき、$x$ と $M$ は互いに素

計算量

• $\Theta(\log{n})\ (n \geq 0)$
• $\Theta(\log{n} + \log{M})\ (n < 0)$

---

ModInt inv()

$x^{-1} \bmod{M}$ を返します。

制約

• $x$ と $M$ は互いに素

計算量

• $\Theta(\log{M})$

---

使用例

#include <bits/stdc++.h>
#include "Mathematics/ModInt.hpp"
using namespace std;

constexpr int MOD = 13;
using mint = ModInt<MOD>;

int main() {
	cout << "M = " << mint::mod() << endl; // 13
	cout << "0: " << mint(0) << endl; // 0
	cout << "15: " << mint(15) << endl; // 2
	cout << "-1: " << mint(-1) << endl; // 12
	cout << "-1: " << mint(-1).val() << endl; // 12
	cout << "10^2 " << mint(10).pow(2) << endl; // 9
	cout << "3^-1 " << mint(3).inv() << endl; // 9 ( 9*3 = 27 = 1+(13*2) )
	
	mint a(10);
	cout << a << endl; // 10
	cout << a + 3 << endl; // 0
	a += 5;
	cout << a << endl; // 2
	a *= 3;
	cout << a << endl; // 6
	a /= 2;
	cout << a << endl; // 3
	a /= 5;
	cout << a << endl; // 11 (5 * 11 = 55 = 3 + 4 * 13)
	a = 5 - a;
	cout << a << endl; // 7
	cout << -a << endl; // 6
	
	a = 10;
	mint b(3);
	cout << a * b << endl; // 4
	
	a = 1;
	b = ++a;
	cout << a << ", " << b << endl; // 2, 2
	a = 1;
	b = a++;
	cout << a << ", " << b << endl; // 2, 1
}

参考

https://noshi91.hatenablog.com/entry/2019/03/31/174006

Verified with

• Test/Combination.test.cpp
• Test/DynamicSegmentTree.test.cpp
• Test/HeavyLightDecomposition_Query.PathQuery.test.cpp
• Test/LazySegmentTree.test.cpp
• Test/SegmentTree.fold.test.cpp
• Test/SlidingWindowAggregation.test.cpp
• Test/VertexUpdatePathFold.vertex.test.cpp
• Test/matrix.det.test.cpp
• Test/matrix.pow.test.cpp

Code

#ifndef INCLUDE_GUARD_MOD_INT_HPP
#define INCLUDE_GUARD_MOD_INT_HPP

#include <cassert>
#include <iostream>
#include <cstdint>

/**
 * @brief https://tkmst201.github.io/Library/Mathematics/ModInt.hpp
 */
template<int M>
struct ModInt {
	static_assert(M > 0);
	
	using value_type = int;
	using calc_type = std::int_fast64_t;
	
private:
	value_type val_;
	
public:
	constexpr ModInt(calc_type val = 0) : val_(val % M + (val >= 0 ? 0 : M)) {}
	constexpr value_type val() const noexcept { return val_; }
	constexpr static decltype(M) mod() noexcept { return M; }
	
	explicit constexpr operator bool() const noexcept { return val_; }
	constexpr bool operator !() const noexcept { return !static_cast<bool>(*this); }
	constexpr ModInt operator +() const noexcept { return *this; }
	constexpr ModInt operator -() const noexcept { return ModInt(val_ == 0 ? 0 : M - val_); }
	constexpr ModInt operator ++(int) noexcept { ModInt res = *this; ++*this; return res; }
	constexpr ModInt operator --(int) noexcept { ModInt res = *this; --*this; return res; }
	constexpr ModInt & operator ++() noexcept { val_ = val_ + 1 == M ? 0 : val_ + 1; return *this; }
	constexpr ModInt & operator --() noexcept { val_ = val_ == 0 ? M - 1 : val_ - 1; return *this; }
	constexpr ModInt & operator +=(const ModInt & rhs) noexcept { val_ += val_ < M - rhs.val_ ? rhs.val_ : rhs.val_ - M; return *this; }
	constexpr ModInt & operator -=(const ModInt & rhs) noexcept { val_ += val_ >= rhs.val_ ? -rhs.val_ : M - rhs.val_; return *this; }
	constexpr ModInt & operator *=(const ModInt & rhs) noexcept { val_ = static_cast<calc_type>(val_) * rhs.val_ % M; return *this; }
	constexpr ModInt & operator /=(const ModInt & rhs) noexcept { return *this *= rhs.inv(); }
	friend constexpr ModInt operator +(const ModInt & lhs, const ModInt & rhs) noexcept { return ModInt(lhs) += rhs; }
	friend constexpr ModInt operator -(const ModInt & lhs, const ModInt & rhs) noexcept { return ModInt(lhs) -= rhs; }
	friend constexpr ModInt operator *(const ModInt & lhs, const ModInt & rhs) noexcept { return ModInt(lhs) *= rhs; }
	friend constexpr ModInt operator /(const ModInt & lhs, const ModInt & rhs) noexcept { return ModInt(lhs) /= rhs; }
	friend constexpr bool operator ==(const ModInt & lhs, const ModInt & rhs) noexcept { return lhs.val_ == rhs.val_; }
	friend constexpr bool operator !=(const ModInt & lhs, const ModInt & rhs) noexcept { return !(lhs == rhs); }
	friend std::ostream & operator <<(std::ostream & os, const ModInt & rhs) { return os << rhs.val_; }
	friend std::istream & operator >>(std::istream & is, ModInt & rhs) { calc_type x; is >> x; rhs = ModInt(x); return is; }
	
	constexpr ModInt pow(calc_type n) const noexcept {
		ModInt res = 1, x = val_;
		if (n < 0) { x = x.inv(); n = -n; }
		while (n) { if (n & 1) res *= x; x *= x; n >>= 1; }
		return res;
	}
	
	constexpr ModInt inv() const noexcept {
		value_type a = val_, a1 = 1, b = M, b1 = 0;
		while (b > 0) {
			const value_type q = a / b;
			value_type tmp = a - q * b; a = b; b = tmp;
			tmp = a1 - q * b1; a1 = b1; b1 = tmp;
		}
		assert(a == 1);
		if (a1 < 0) a1 += M;
		return a1;
	}
};

#endif // INCLUDE_GUARD_MOD_INT_HPP

#line 1 "Mathematics/ModInt.hpp"



#include <cassert>
#include <iostream>
#include <cstdint>

/**
 * @brief https://tkmst201.github.io/Library/Mathematics/ModInt.hpp
 */
template<int M>
struct ModInt {
	static_assert(M > 0);
	
	using value_type = int;
	using calc_type = std::int_fast64_t;
	
private:
	value_type val_;
	
public:
	constexpr ModInt(calc_type val = 0) : val_(val % M + (val >= 0 ? 0 : M)) {}
	constexpr value_type val() const noexcept { return val_; }
	constexpr static decltype(M) mod() noexcept { return M; }
	
	explicit constexpr operator bool() const noexcept { return val_; }
	constexpr bool operator !() const noexcept { return !static_cast<bool>(*this); }
	constexpr ModInt operator +() const noexcept { return *this; }
	constexpr ModInt operator -() const noexcept { return ModInt(val_ == 0 ? 0 : M - val_); }
	constexpr ModInt operator ++(int) noexcept { ModInt res = *this; ++*this; return res; }
	constexpr ModInt operator --(int) noexcept { ModInt res = *this; --*this; return res; }
	constexpr ModInt & operator ++() noexcept { val_ = val_ + 1 == M ? 0 : val_ + 1; return *this; }
	constexpr ModInt & operator --() noexcept { val_ = val_ == 0 ? M - 1 : val_ - 1; return *this; }
	constexpr ModInt & operator +=(const ModInt & rhs) noexcept { val_ += val_ < M - rhs.val_ ? rhs.val_ : rhs.val_ - M; return *this; }
	constexpr ModInt & operator -=(const ModInt & rhs) noexcept { val_ += val_ >= rhs.val_ ? -rhs.val_ : M - rhs.val_; return *this; }
	constexpr ModInt & operator *=(const ModInt & rhs) noexcept { val_ = static_cast<calc_type>(val_) * rhs.val_ % M; return *this; }
	constexpr ModInt & operator /=(const ModInt & rhs) noexcept { return *this *= rhs.inv(); }
	friend constexpr ModInt operator +(const ModInt & lhs, const ModInt & rhs) noexcept { return ModInt(lhs) += rhs; }
	friend constexpr ModInt operator -(const ModInt & lhs, const ModInt & rhs) noexcept { return ModInt(lhs) -= rhs; }
	friend constexpr ModInt operator *(const ModInt & lhs, const ModInt & rhs) noexcept { return ModInt(lhs) *= rhs; }
	friend constexpr ModInt operator /(const ModInt & lhs, const ModInt & rhs) noexcept { return ModInt(lhs) /= rhs; }
	friend constexpr bool operator ==(const ModInt & lhs, const ModInt & rhs) noexcept { return lhs.val_ == rhs.val_; }
	friend constexpr bool operator !=(const ModInt & lhs, const ModInt & rhs) noexcept { return !(lhs == rhs); }
	friend std::ostream & operator <<(std::ostream & os, const ModInt & rhs) { return os << rhs.val_; }
	friend std::istream & operator >>(std::istream & is, ModInt & rhs) { calc_type x; is >> x; rhs = ModInt(x); return is; }
	
	constexpr ModInt pow(calc_type n) const noexcept {
		ModInt res = 1, x = val_;
		if (n < 0) { x = x.inv(); n = -n; }
		while (n) { if (n & 1) res *= x; x *= x; n >>= 1; }
		return res;
	}
	
	constexpr ModInt inv() const noexcept {
		value_type a = val_, a1 = 1, b = M, b1 = 0;
		while (b > 0) {
			const value_type q = a / b;
			value_type tmp = a - q * b; a = b; b = tmp;
			tmp = a1 - q * b1; a1 = b1; b1 = tmp;
		}
		assert(a == 1);
		if (a1 < 0) a1 += M;
		return a1;
	}
};

Back to top page