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

• View this file on GitHub
• Last update: 2020-04-22 01:19:00+09:00
• Include: #include "math/extgcd.hpp"

概要

与えられた$a, b$に対して, 最大公約数$gcd(a, b)$と, $ax + by = gcd(a, b)$なる$x, y$を求める.

計算量

$O(\log a)$

使用例

• extgcd(a, b, x, y) : $a$と$b$に対して拡張ユークリッドの互除法を行う.
  • $ax + by = gcd(a, b)$なる$x, y$はx, yに格納される.
  • 返り値 : $gcd(a, b)$

Verified with

• test/aoj/NTL_1_E.test.cpp

Code

/**
* @brief 拡張ユークリッドの互除法
* @docs docs/math/extgcd.md
*/

long long extgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = extgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

#line 1 "math/extgcd.hpp"
/**
* @brief 拡張ユークリッドの互除法
* @docs docs/math/extgcd.md
*/

long long extgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = extgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

Back to top page