拡張ユークリッドの互除法 (src/math/extended_gcd.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2023-08-31 15:37:54+09:00
• Include: #include "src/math/extended_gcd.hpp"

Verified with

• test/math/extended_gcd/aoj_ntl_1_e.test.cpp

Code

#ifndef MATH_EXTENDED_GCD_HPP
#define MATH_EXTENDED_GCD_HPP

template<class T>
T extended_gcd(T a, T b, T &x, T &y) { // ax+by=gcd(a,b)
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	T d = extended_gcd(b, a % b, y, x);
	y -= a / b * x;
	return d;
}

template<class T>
T modinv(T a, T mod) { // a,modは互いに素
	T x, y;
	extended_gcd(a, mod, x, y);
	return (x % mod + mod) % mod;
}

#endif // MATH_EXTENDED_GCD_HPP

#line 1 "src/math/extended_gcd.hpp"



template<class T>
T extended_gcd(T a, T b, T &x, T &y) { // ax+by=gcd(a,b)
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	T d = extended_gcd(b, a % b, y, x);
	y -= a / b * x;
	return d;
}

template<class T>
T modinv(T a, T mod) { // a,modは互いに素
	T x, y;
	extended_gcd(a, mod, x, y);
	return (x % mod + mod) % mod;
}

Back to top page