library/math/pow-mod.hpp

• View this file on GitHub
• Last update: 2023-05-28 03:49:52+08:00
• Include: #include "library/math/pow-mod.hpp"

Depends on

• library/math/safe-mod.hpp
• library/misc/type-traits.hpp

Required by

• library/convolution/ntt.hpp
• library/formal-power-series/poly.hpp
• Integer Factorization (Pollard Rho 質因數分解) (library/math/factorize.hpp)
• library/math/is-prime.hpp
• library/math/primitive-root.hpp

Verified with

• test/convolution/ntt/yosupo-Convolution-Large.test.cpp
• test/convolution/ntt/yosupo-Convolution-Mod-1000000007.test.cpp
• test/convolution/ntt/yosupo-Convolution.test.cpp
• test/formal-power-series/poly/yosupo-Exp-of-Formal-Power-Series.test.cpp
• test/formal-power-series/poly/yosupo-Inv-of-Formal-Power-Series.test.cpp
• test/formal-power-series/poly/yosupo-Log-of-Formal-Power-Series.test.cpp
• test/formal-power-series/poly/yosupo-Multipoint-Evaluation.test.cpp
• test/formal-power-series/poly/yosupo-Polynomial-Taylor-Shift.test.cpp
• test/formal-power-series/poly/yosupo-Pow-of-Formal-Power-Series.test.cpp
• test/formal-power-series/poly/yosupo-Product-of-Polynomial-Sequence.test.cpp
• test/formal-power-series/poly/yosupo-Sqrt-of-Formal-Power-Series.test.cpp
• test/formal-power-series/series/yosupo-Partition-Function.test.cpp
• test/math/factorize/aoj-ntl-Prime-Factorize.test.cpp
• test/math/factorize/yosupo-Factorize.test.cpp
• test/math/is-prime/yosupo-Primality-Test.test.cpp

Code

#pragma once
#include "../misc/type-traits.hpp"

#include "safe-mod.hpp"


namespace felix {

namespace internal {

template<class T>
constexpr T pow_mod_constexpr(T x, long long n, T m) {
	using U = safely_multipliable_t<T>;
	if(m == 1) {
		return 0;
	}
	U r = 1, y = safe_mod(x, m);
	while(n) {
		if(n & 1) {
			r = (r * y) % m;
		}
		y = (y * y) % m;
		n >>= 1;
	}
	return r;
}

} // namespace internal


} // namespace felix

#line 2 "library/misc/type-traits.hpp"
#include <cassert>

#include <numeric>

#include <type_traits>


namespace felix {

namespace internal {

#ifndef _MSC_VER
template<class T> using is_signed_int128 = typename std::conditional<std::is_same<T, __int128_t>::value || std::is_same<T, __int128>::value, std::true_type, std::false_type>::type;
template<class T> using is_unsigned_int128 = typename std::conditional<std::is_same<T, __uint128_t>::value || std::is_same<T, unsigned __int128>::value, std::true_type, std::false_type>::type;
template<class T> using make_unsigned_int128 = typename std::conditional<std::is_same<T, __int128_t>::value, __uint128_t, unsigned __int128>;
template<class T> using is_integral = typename std::conditional<std::is_integral<T>::value || is_signed_int128<T>::value || is_unsigned_int128<T>::value, std::true_type, std::false_type>::type;
template<class T> using is_signed_int = typename std::conditional<(is_integral<T>::value && std::is_signed<T>::value) || is_signed_int128<T>::value, std::true_type, std::false_type>::type;
template<class T> using is_unsigned_int = typename std::conditional<(is_integral<T>::value && std::is_unsigned<T>::value) || is_unsigned_int128<T>::value, std::true_type, std::false_type>::type;
template<class T> using to_unsigned = typename std::conditional<is_signed_int128<T>::value, make_unsigned_int128<T>, typename std::conditional<std::is_signed<T>::value, std::make_unsigned<T>, std::common_type<T>>::type>::type;
#else
template<class T> using is_integral = typename std::is_integral<T>;
template<class T> using is_signed_int = typename std::conditional<is_integral<T>::value && std::is_signed<T>::value, std::true_type, std::false_type>::type;
template<class T> using is_unsigned_int = typename std::conditional<is_integral<T>::value && std::is_unsigned<T>::value, std::true_type, std::false_type>::type;
template<class T> using to_unsigned = typename std::conditional<is_signed_int<T>::value, std::make_unsigned<T>, std::common_type<T>>::type;
#endif

template<class T> using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
template<class T> using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
template<class T> using to_unsigned_t = typename to_unsigned<T>::type;

template<class T> struct safely_multipliable {};
template<> struct safely_multipliable<short> { using type = int; };
template<> struct safely_multipliable<unsigned short> { using type = unsigned int; };
template<> struct safely_multipliable<int> { using type = long long; };
template<> struct safely_multipliable<unsigned int> { using type = unsigned long long; };
template<> struct safely_multipliable<long long> { using type = __int128; };
template<> struct safely_multipliable<unsigned long long> { using type = __uint128_t; };

template<class T> using safely_multipliable_t = typename safely_multipliable<T>::type;

}  // namespace internal


}  // namespace felix

#line 2 "library/math/safe-mod.hpp"

namespace felix {

namespace internal {

template<class T>
constexpr T safe_mod(T x, T m) {
	x %= m;
	if(x < 0) {
		x += m;
	}
	return x;
}

} // namespace internal


} // namespace felix
#line 4 "library/math/pow-mod.hpp"

namespace felix {

namespace internal {

template<class T>
constexpr T pow_mod_constexpr(T x, long long n, T m) {
	using U = safely_multipliable_t<T>;
	if(m == 1) {
		return 0;
	}
	U r = 1, y = safe_mod(x, m);
	while(n) {
		if(n & 1) {
			r = (r * y) % m;
		}
		y = (y * y) % m;
		n >>= 1;
	}
	return r;
}

} // namespace internal


} // namespace felix

Back to top page