This documentation is automatically generated by online-judge-tools/verification-helper
#include "math/number-theory/extgcd.hpp"
T extgcd(T a, T b, T &x, T &y)
$\gcd(a, b)$ を返します。$(x, y)$ には $ax + by = \gcd(a, b)$ を満たす整数解が格納されます。整数解は複数考えられますが、$|x| + |y|$ が最小のものが格納されます。
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/number-theory/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;
}