library/math/inv-gcd.hpp

• View this file on GitHub
• Last update: 2023-04-21 21:20:30+08:00
• Include: #include "library/math/inv-gcd.hpp"
• Link: View error logs on GitHub Actions

Depends on

• library/math/safe-mod.hpp

Required by

• library/convolution/ntt.hpp
• library/formal-power-series/poly.hpp
• Chinese Remainder Theorem (中國剩餘定理) (library/math/crt.hpp)
• library/modint/modint.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/convolution/subset-convolution/yosupo-Bitwise-And-Convolution.test.cpp
• test/convolution/subset-convolution/yosupo-Bitwise-Xor-Convolution.test.cpp
• test/convolution/subset-convolution/yosupo-Subset-Convolution.test.cpp
• test/data-structure/lazy-lct/yosupo-Dynamic-Tree-Vertex-Set-Path-Composite.test.cpp
• test/data-structure/lazy-segtree/yosupo-Range-Affine-Point-Get.test.cpp
• test/data-structure/lazy-segtree/yosupo-Range-Affine-Range-Sum.test.cpp
• test/data-structure/treap/yosupo-Dynamic-Sequence-Range-Affine-Range-Sum.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/matrix/matrix/yosupo-Determinant-of-Matrix.test.cpp
• test/matrix/matrix/yosupo-Matrix-Product.test.cpp
• test/modint/modint/aoj-ntl-Power.test.cpp
• test/modint/modint/yosupo-Sqrt-Mod.test.cpp
• test/tree/hld/yosupo-Vertex-Set-Path-Composite.test.cpp

Code

#pragma once
#include "safe-mod.hpp"


namespace felix {

namespace internal {

template<class T>
constexpr std::pair<T, T> inv_gcd(T a, T b) {
	a = safe_mod(a, b);
	if(a == 0) {
		return {b, 0};
	}
	T s = b, t = a;
	T m0 = 0, m1 = 1;
	while(t) {
		T u = s / t;
		s -= t * u;
		m0 -= m1 * u;
		auto tmp = s;
		s = t;
		t = tmp;
		tmp = m0;
		m0 = m1;
		m1 = tmp;
	}
	if(m0 < 0) {
		m0 += b / s;
	}
	return {s, m0};
}

} // 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 3 "library/math/inv-gcd.hpp"

namespace felix {

namespace internal {

template<class T>
constexpr std::pair<T, T> inv_gcd(T a, T b) {
	a = safe_mod(a, b);
	if(a == 0) {
		return {b, 0};
	}
	T s = b, t = a;
	T m0 = 0, m1 = 1;
	while(t) {
		T u = s / t;
		s -= t * u;
		m0 -= m1 * u;
		auto tmp = s;
		s = t;
		t = tmp;
		tmp = m0;
		m0 = m1;
		m1 = tmp;
	}
	if(m0 < 0) {
		m0 += b / s;
	}
	return {s, m0};
}

} // namespace internal


} // namespace felix

Back to top page