$\mod{m}$ での冪と逆元
(Mathematics/mod_pow_inv.hpp)

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

概要

整数 $a, x, m$ に対して $a^x \pmod{m}$ や $a^{-1} \pmod{m}$ を求めます。

関数

T mod_pow(T x, T n, T m)

整数 $x, n, m$ に対して $x^n \pmod{m}$ を返します。

制約

• T は int, unsigned int, long long, unsigned long long
• $m^2$ が T で表現可能
• $0 \leq n$
• $0 < m$

計算量

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

---

T mod_inv(T x, T m)

整数 $x, m$ に対して $x^{-1} \pmod{m}$ を返します。

制約

• T は int, long long
• $0 < m$
• $x$ と $m$ は互いに素

計算量

• $\mathcal{O}(\log{\min(x, m)})$

---

使用例

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

int main() {
	cout << "mod_pow(2, 3, 3) = " << tk::mod_pow(2, 3, 3) << endl; // 2 (2^3 = 8)
	cout << "mod_pow(5, 0, 10) = " << tk::mod_pow(2, 3, 3) << endl; // 1 (5^0 = 1)
	cout << "mod_pow(10, 2, 10000) = " << tk::mod_pow(10, 2, 10000) << endl; // 100 (10^2 = 100)
	
	cout << "mod_inv(10, 7) = " << tk::mod_inv(10, 7) << endl; // -2 (10*(-2) = -20 = 7*(-3) + 1)
	cout << "mod_inv(4, 3) = " << tk::mod_inv(4, 3) << endl; // 1 (4*1 = 3*1 + 1)
	cout << "mod_inv(-5, 8) = " << tk::mod_inv(-5, 8) << endl; // 3 (-5*3 = 8*(-2) + 1)
}

参考

2020/01/14: https://noshi91.hatenablog.com/entry/2019/04/01/184957

Required by

• 数論変換 (NTT) (Convolution/NumberTheoreticTransform.hpp)
• 任意 mod 数論変換 (任意 mod NTT) (Convolution/NumberTheoreticTransform_AnyMod.hpp)
• Garner (連立一次合同式 mod M) (Mathematics/garner.hpp)

Verified with

• Test/NumberTheoreticTransform.test.cpp
• Test/NumberTheoreticTransform_AnyMod.test.cpp
• Test/garner.test.cpp

Code

#ifndef INCLUDE_GUARD_MOD_POW_INV_HPP
#define INCLUDE_GUARD_MOD_POW_INV_HPP

#include <cassert>
#include <type_traits>

/**
 * @brief https://tkmst201.github.io/Library/Mathematics/mod_pow_inv.hpp
 */
namespace tk {
template<typename T>
constexpr T mod_pow(T x, T n, T m) noexcept {
	static_assert(std::is_integral<T>::value);
	assert(m > 0);
	assert(n >= 0);
	x = x % m + (x >= 0 ? 0 : m);
	T res = 1 % m;
	while (n > 0) {
		if (n & 1) res = res * x % m;
		x = x * x % m;
		n >>= 1;
	}
	return res;
}

template<typename T>
constexpr T mod_inv(T x, T m) noexcept {
	static_assert(std::is_integral<T>::value);
	static_assert(std::is_signed<T>::value);
	assert(m > 0);
	x = x % m + (x >= 0 ? 0 : m);
	T x1 = 1, y = m, y1 = 0;
	while (y > 0) {
		const T q = x / y;
		T tmp = x - q * y; x = y; y = tmp;
		tmp = x1 - q * y1; x1 = y1; y1 = tmp;
	}
	assert(x == 1);
	if (x1 == m) x1 = 0;
	if (x1 < 0) x1 += m;
	return x1;
}
} // namespace tk


#endif // INCLUDE_GUARD_MOD_POW_INV_HPP

#line 1 "Mathematics/mod_pow_inv.hpp"



#include <cassert>
#include <type_traits>

/**
 * @brief https://tkmst201.github.io/Library/Mathematics/mod_pow_inv.hpp
 */
namespace tk {
template<typename T>
constexpr T mod_pow(T x, T n, T m) noexcept {
	static_assert(std::is_integral<T>::value);
	assert(m > 0);
	assert(n >= 0);
	x = x % m + (x >= 0 ? 0 : m);
	T res = 1 % m;
	while (n > 0) {
		if (n & 1) res = res * x % m;
		x = x * x % m;
		n >>= 1;
	}
	return res;
}

template<typename T>
constexpr T mod_inv(T x, T m) noexcept {
	static_assert(std::is_integral<T>::value);
	static_assert(std::is_signed<T>::value);
	assert(m > 0);
	x = x % m + (x >= 0 ? 0 : m);
	T x1 = 1, y = m, y1 = 0;
	while (y > 0) {
		const T q = x / y;
		T tmp = x - q * y; x = y; y = tmp;
		tmp = x1 - q * y1; x1 = y1; y1 = tmp;
	}
	assert(x == 1);
	if (x1 == m) x1 = 0;
	if (x1 < 0) x1 += m;
	return x1;
}
} // namespace tk

Back to top page