library/math/primitive-root.hpp

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

Depends on

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

Required by

• library/convolution/ntt.hpp
• library/formal-power-series/poly.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

Code

#pragma once
#include <cassert>
#include "pow-mod.hpp"

namespace felix {

namespace internal {

constexpr int primitive_root_constexpr(int m) {
	if(m == 998244353) return 3;
	if(m == 167772161) return 3;
	if(m == 469762049) return 3;
	if(m == 754974721) return 11;
	if(m == 2) return 1;
	int divs[20] = {};
	divs[0] = 2;
	int cnt = 1;
	int x = (m - 1) / 2;
	x >>= __builtin_ctz(x);
	for(int i = 3; 1LL * i * i <= x; i += 2) {
		if(x % i == 0) {
			divs[cnt++] = i;
			while(x % i == 0) {
				x /= i;
			}
		}
	}
	if(x > 1) {
		divs[cnt++] = x;
	}
	for(int g = 2;; g++) {
		bool ok = true;
		for(int i = 0; i < cnt; i++) {
			if(pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
				ok = false;
				break;
			}
		}
		if(ok) {
			return g;
		}
	}
	assert(false);
}

} // namespace internal

} // namespace felix

#line 2 "library/math/primitive-root.hpp"
#include <cassert>
#line 3 "library/misc/type-traits.hpp"
#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

#line 4 "library/math/primitive-root.hpp"

namespace felix {

namespace internal {

constexpr int primitive_root_constexpr(int m) {
	if(m == 998244353) return 3;
	if(m == 167772161) return 3;
	if(m == 469762049) return 3;
	if(m == 754974721) return 11;
	if(m == 2) return 1;
	int divs[20] = {};
	divs[0] = 2;
	int cnt = 1;
	int x = (m - 1) / 2;
	x >>= __builtin_ctz(x);
	for(int i = 3; 1LL * i * i <= x; i += 2) {
		if(x % i == 0) {
			divs[cnt++] = i;
			while(x % i == 0) {
				x /= i;
			}
		}
	}
	if(x > 1) {
		divs[cnt++] = x;
	}
	for(int g = 2;; g++) {
		bool ok = true;
		for(int i = 0; i < cnt; i++) {
			if(pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
				ok = false;
				break;
			}
		}
		if(ok) {
			return g;
		}
	}
	assert(false);
}

} // namespace internal

} // namespace felix

Back to top page