定数時間 mod inv

math/mod_inv.hpp · GitHub で見る

共通ページ · 軽量実装なし

#include "lib/math/mod_inv.hpp"

ModInv inverse(17);
auto x = inverse.inv(3); // 6

操作	内容・返り値	計算量
ModInv(prime = 998244353)	素数を固定し、逆元用の表を前計算	\(O(p^{2/3})\)
mod()	法を uint32_t で返す	\(O(1)\)
inv(x)	\(x^{-1}\bmod p\) を uint32_t で返す。\(1\le x<p\)	\(O(1)\)

法 \(p\) は \(2\le p<2^{31}\) の素数です。法は実行時に指定できます。引数は正規化済みの uint32_t を渡し、0 の逆元は扱いません。多数のクエリで同じオブジェクトを使い回します。既存の mint と組み合わせる場合は mint::raw(inverse.inv(a.val())) とします。

返り値 y = inverse.inv(x) は \(xy\equiv1\pmod p\) を満たします。上の例は \(3\cdot6\equiv1\pmod{17}\) です。コンストラクタで前計算するため、クエリのたびにオブジェクトを作る必要はありません。

小さい分子・分母による有理数表現と逆元表を前計算するため、クエリ時に Euclid の互除法や繰り返し二乗法を行いません。累乗も必要なら、逆元機能を含む ModPow を使います。

前計算は \(O(p^{2/3})\) 時間・空間、mod・inv は \(O(1)\) 時間です。

依存ライブラリ

• 素数判定の基数表
• 素数判定の共通演算
• 定数時間 mod 演算の内部部品
• Montgomery 64
• Montgomery 32
• 素数判定（高速版）

検証コード

• test/mod_pow_log.test.cpp

コード

#ifndef MOD_INV_HPP
#define MOD_INV_HPP

#include "../components/mod_fast_core.hpp"
#include "is_prime.hpp"

class ModInv {
  protected:
	mod_fast_detail::Reducer modulus_;
	mod_fast_detail::RationalTable fractions_;
	std::vector<std::uint32_t> inverse_;
	int center_;

  public:
	explicit ModInv(std::uint32_t prime = 998244353) : modulus_(prime), fractions_(prime), center_(fractions_.direct() ? 0 : fractions_.limit()) {
		assert(is_prime(prime));
		std::uint32_t limit = fractions_.limit();
		inverse_.resize(center_ + limit + 1);
		inverse_[center_ + 1] = 1;
		for (std::uint32_t i = 2; i <= limit; ++i)
			inverse_[center_ + i] = prime - modulus_.mul(prime / i, inverse_[center_ + prime % i]);
		if (center_) for (std::uint32_t i = 1; i <= limit; ++i) inverse_[center_ - i] = prime - inverse_[center_ + i];
	}
	std::uint32_t mod() const { return modulus_.mod; }
	std::uint32_t inv(std::uint32_t x) const {
		assert(0 < x && x < mod());
		if (x <= fractions_.limit()) return inverse_[center_ + x];
		auto [a, b] = fractions_.fraction(x);
		return modulus_.mul(inverse_[center_ + a], b);
	}
};

#endif

Back to top page