mmrz's library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by mm-rz Hosted on GitHub Pages — Theme by mattgraham

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

• View this file on GitHub
• Last update: 2025-05-27 00:04:09+09:00
• Include: #include "math/extgcd.hpp"

拡張ユークリッドの互除法

使い方

extgcd(T a, T b, T &x, T &y) : $ax + by = \text{gcd}(a, b)$ なる $x, y$ を求める。$O(\log{a+b})$ 程度

Verified with

• verify/aoj/id/3362.test.cpp
• verify/aoj/ntl/1_E.test.cpp

Code

template<typename T>
T extgcd(T a, T b, T &x, T &y){
	T d = a;
	if(b != 0){
		d = extgcd(b, a%b, y, x);
		y -= (a/b) * x;
	}else{
		x = 1;
		y = 0;
	}
	return d;
}

#line 1 "math/extgcd.hpp"

template<typename T>
T extgcd(T a, T b, T &x, T &y){
	T d = a;
	if(b != 0){
		d = extgcd(b, a%b, y, x);
		y -= (a/b) * x;
	}else{
		x = 1;
		y = 0;
	}
	return d;
}

Back to top page