ModInt 構造体 (実行時 mod 指定)
(Mathematics/RuntimeModInt.hpp)

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

概要

実行時に法 $M$ を指定する ModInt 構造体です。
ModInt が渡せるほとんどのライブラリで用いることができます。

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

コンストラクタ

$ID$ に渡す値によって mod を区別することができます。詳しくは使用例を参照してください。

RuntimeModInt(long long val = 0)

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

計算量

$\Theta(1)$

演算

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

+RuntimeModInt
-RuntimeModInt

RuntimeModInt++
RuntimeModInt--

++RuntimeModInt
--RuntimeModInt

RuntimeModInt += RuntimeModInt
RuntimeModInt -= RuntimeModInt
RuntimeModInt *= RuntimeModInt
RuntimeModInt /= RuntimeModInt

RuntimeModInt + RuntimeModInt
RuntimeModInt - RuntimeModInt
RuntimeModInt * RuntimeModInt
RuntimeModInt / RuntimeModInt

bool(RuntimeModInt)
!RuntimeModInt
RuntimeModInt == RuntimeModInt
RuntimeModInt != RuntimeModInt

std::cin >> RuntimeModInt
std::cout << RuntimeModInt

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

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

制約

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

計算量

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

メンバ関数

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

static void set_mod(int M)

法 $M$ を設定します。

制約

$0 < M$

計算量

$\Theta(1)$

static int mod()

$M$ を返します。

計算量

$\Theta(1)$

int val()

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

計算量

$\Theta(1)$

RuntimeModInt 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)$

RuntimeModInt inv()

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

制約

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

計算量

$\Theta(\log{M})$

使用例

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

using mint1 = RuntimeModInt<0>;
using mint2 = RuntimeModInt<1>;

int main() {
	mint1::set_mod(7);
	mint2::set_mod(13);
	
	cout << "M1 = " << mint1::mod() << ", M2 = " << mint2::mod() << endl; // 7, 13
	cout << mint1(100) << ", " << mint2(100) << endl; // 2, 9
	
	cout << "0: " << mint2(0) << endl; // 0
	cout << "15: " << mint2(15) << endl; // 2
	cout << "-1: " << mint2(-1) << endl; // 12
	cout << "-1: " << mint2(-1).val() << endl; // 12
	
	mint2 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;
	mint2 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
}

TODO

TODO: test の追加

参考

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

Code

#ifndef INCLUDE_GUARD_RUNTIME_MOD_INT_HPP
#define INCLUDE_GUARD_RUNTIME_MOD_INT_HPP


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

/**
 * @brief https://tkmst201.github.io/Library/Mathematics/RuntimeModInt.hpp
 */
template<int ID>
struct RuntimeModInt {
	using value_type = int;
	using calc_type = std::int_fast64_t;
	
private:
	value_type val_;
	static int & mod_() noexcept { static int M = 2; return M; }
	
public:
	RuntimeModInt(calc_type val = 0) : val_(val % mod() + (val >= 0 ? 0 : mod())) {}
	const value_type val() const noexcept { return val_; }
	static void set_mod(int M) noexcept { assert(M > 0); mod_() = M; }
	static int mod() noexcept { return mod_(); }
	
	explicit operator bool() const noexcept { return val_; }
	bool operator !() const noexcept { return !static_cast<bool>(*this); }
	RuntimeModInt operator +() const noexcept { return *this; }
	RuntimeModInt operator -() const noexcept { return RuntimeModInt(val_ == 0 ? 0 : mod() - val_); }
	RuntimeModInt operator ++(int) noexcept { RuntimeModInt res = *this; ++*this; return res; }
	RuntimeModInt operator --(int) noexcept { RuntimeModInt res = *this; --*this; return res; }
	RuntimeModInt & operator ++() noexcept { val_ = val_ + 1 == mod() ? 0 : val_ + 1; return *this; }
	RuntimeModInt & operator --() noexcept { val_ = val_ == 0 ? mod() - 1 : val_ - 1; return *this; }
	RuntimeModInt & operator +=(const RuntimeModInt & rhs) noexcept { val_ += val_ < mod() - rhs.val_ ? rhs.val_ : rhs.val_ - mod(); return *this; }
	RuntimeModInt & operator -=(const RuntimeModInt & rhs) noexcept { val_ += val_ >= rhs.val_ ? -rhs.val_ : mod() - rhs.val_; return *this; }
	RuntimeModInt & operator *=(const RuntimeModInt & rhs) noexcept { val_ = static_cast<calc_type>(val_) * rhs.val_ % mod(); return *this; }
	RuntimeModInt & operator /=(const RuntimeModInt & rhs) noexcept { return *this *= rhs.inv(); }
	friend RuntimeModInt operator +(const RuntimeModInt & lhs, const RuntimeModInt & rhs) noexcept { return RuntimeModInt(lhs) += rhs; }
	friend RuntimeModInt operator -(const RuntimeModInt & lhs, const RuntimeModInt & rhs) noexcept { return RuntimeModInt(lhs) -= rhs; }
	friend RuntimeModInt operator *(const RuntimeModInt & lhs, const RuntimeModInt & rhs) noexcept { return RuntimeModInt(lhs) *= rhs; }
	friend RuntimeModInt operator /(const RuntimeModInt & lhs, const RuntimeModInt & rhs) noexcept { return RuntimeModInt(lhs) /= rhs; }
	friend bool operator ==(const RuntimeModInt & lhs, const RuntimeModInt & rhs) noexcept { return lhs.val_ == rhs.val_; }
	friend bool operator !=(const RuntimeModInt & lhs, const RuntimeModInt & rhs) noexcept { return !(lhs == rhs); }
	friend std::ostream & operator <<(std::ostream & os, const RuntimeModInt & rhs) { return os << rhs.val_; }
	friend std::istream & operator >>(std::istream & is, RuntimeModInt & rhs) { calc_type x; is >> x; rhs = RuntimeModInt(x); return is; }
	
	RuntimeModInt pow(calc_type n) const noexcept {
		RuntimeModInt 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;
	}
	
	RuntimeModInt inv() const noexcept {
		value_type a = val_, a1 = 1, b = mod(), 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 += mod();
		return a1;
	}
};

#endif // INCLUDE_GUARD_RUNTIME_MOD_INT_HPP

#line 1 "Mathematics/RuntimeModInt.hpp"




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

/**
 * @brief https://tkmst201.github.io/Library/Mathematics/RuntimeModInt.hpp
 */
template<int ID>
struct RuntimeModInt {
	using value_type = int;
	using calc_type = std::int_fast64_t;
	
private:
	value_type val_;
	static int & mod_() noexcept { static int M = 2; return M; }
	
public:
	RuntimeModInt(calc_type val = 0) : val_(val % mod() + (val >= 0 ? 0 : mod())) {}
	const value_type val() const noexcept { return val_; }
	static void set_mod(int M) noexcept { assert(M > 0); mod_() = M; }
	static int mod() noexcept { return mod_(); }
	
	explicit operator bool() const noexcept { return val_; }
	bool operator !() const noexcept { return !static_cast<bool>(*this); }
	RuntimeModInt operator +() const noexcept { return *this; }
	RuntimeModInt operator -() const noexcept { return RuntimeModInt(val_ == 0 ? 0 : mod() - val_); }
	RuntimeModInt operator ++(int) noexcept { RuntimeModInt res = *this; ++*this; return res; }
	RuntimeModInt operator --(int) noexcept { RuntimeModInt res = *this; --*this; return res; }
	RuntimeModInt & operator ++() noexcept { val_ = val_ + 1 == mod() ? 0 : val_ + 1; return *this; }
	RuntimeModInt & operator --() noexcept { val_ = val_ == 0 ? mod() - 1 : val_ - 1; return *this; }
	RuntimeModInt & operator +=(const RuntimeModInt & rhs) noexcept { val_ += val_ < mod() - rhs.val_ ? rhs.val_ : rhs.val_ - mod(); return *this; }
	RuntimeModInt & operator -=(const RuntimeModInt & rhs) noexcept { val_ += val_ >= rhs.val_ ? -rhs.val_ : mod() - rhs.val_; return *this; }
	RuntimeModInt & operator *=(const RuntimeModInt & rhs) noexcept { val_ = static_cast<calc_type>(val_) * rhs.val_ % mod(); return *this; }
	RuntimeModInt & operator /=(const RuntimeModInt & rhs) noexcept { return *this *= rhs.inv(); }
	friend RuntimeModInt operator +(const RuntimeModInt & lhs, const RuntimeModInt & rhs) noexcept { return RuntimeModInt(lhs) += rhs; }
	friend RuntimeModInt operator -(const RuntimeModInt & lhs, const RuntimeModInt & rhs) noexcept { return RuntimeModInt(lhs) -= rhs; }
	friend RuntimeModInt operator *(const RuntimeModInt & lhs, const RuntimeModInt & rhs) noexcept { return RuntimeModInt(lhs) *= rhs; }
	friend RuntimeModInt operator /(const RuntimeModInt & lhs, const RuntimeModInt & rhs) noexcept { return RuntimeModInt(lhs) /= rhs; }
	friend bool operator ==(const RuntimeModInt & lhs, const RuntimeModInt & rhs) noexcept { return lhs.val_ == rhs.val_; }
	friend bool operator !=(const RuntimeModInt & lhs, const RuntimeModInt & rhs) noexcept { return !(lhs == rhs); }
	friend std::ostream & operator <<(std::ostream & os, const RuntimeModInt & rhs) { return os << rhs.val_; }
	friend std::istream & operator >>(std::istream & is, RuntimeModInt & rhs) { calc_type x; is >> x; rhs = RuntimeModInt(x); return is; }
	
	RuntimeModInt pow(calc_type n) const noexcept {
		RuntimeModInt 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;
	}
	
	RuntimeModInt inv() const noexcept {
		value_type a = val_, a1 = 1, b = mod(), 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 += mod();
		return a1;
	}
};

ModInt 構造体 (実行時 mod 指定) (Mathematics/RuntimeModInt.hpp)

概要

コンストラクタ

RuntimeModInt(long long val = 0)

演算

メンバ関数

static void set_mod(int M)

static int mod()

int val()

RuntimeModInt pow(long long n)

RuntimeModInt inv()

使用例

TODO

参考

Code

ModInt 構造体 (実行時 mod 指定)
(Mathematics/RuntimeModInt.hpp)