#include "Math/Number-Theory/extgcd.hpp"
#pragma once /** * @brief extgcd() (拡張ユークリッドの互除法) * ax + by = gcd(a, b) の整数解 (x, y) を引数に格納する */ template <class T> T extgcd(T a, T b, T& x, T& y) { T g = a; if (b != 0) { g = extgcd(b, a % b, y, x); y -= (a / b) * x; } else { x = 1; y = 0; } return g; }
#line 2 "Math/Number-Theory/extgcd.hpp" /** * @brief extgcd() (拡張ユークリッドの互除法) * ax + by = gcd(a, b) の整数解 (x, y) を引数に格納する */ template <class T> T extgcd(T a, T b, T& x, T& y) { T g = a; if (b != 0) { g = extgcd(b, a % b, y, x); y -= (a / b) * x; } else { x = 1; y = 0; } return g; }