This documentation is automatically generated by online-judge-tools/verification-helper
#include "Mathematics/ModInt.hpp"
自動で mod を取ってくれる構造体です。
基本的な四則演算や std::cin
、std::cout
に対応しています。
int
が渡せるほとんどのライブラリで用いることができます。
ModInt(long long val = 0)
static int mod()
int val()
ModInt pow(long long n)
ModInt inv()
mod に取りたい値を $M$ に渡します。
制約
$val \bmod{M}$ で初期化します。 何も指定しない場合の初期値は $0$ です。
計算量
以下の演算が使用可能です。
+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$ は互いに素計算量
ModInt /= ModInt
または ModInt / ModInt
)以下、保持している値を $x$ とします。
$M$ を返します。
計算量
$x \bmod{M}$ を返します。
計算量
$x^n \bmod{M}$ を返します。
制約
計算量
$x^{-1} \bmod{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
#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;
}
};