a * x + b * y == gcd(a, b)を満たす x, y を見つける
(Math/extended_gcd.hpp)

• View this file on GitHub
• Last update: 2025-03-11 07:02:05+09:00
• Include: #include "Math/extended_gcd.hpp"

Required by

• a の mod m における逆元 x を求める (Math/BinomMod_ll.hpp)

Code

#ifndef H_extended_gcd
#define H_extended_gcd

/**
 * @brief a * x + b * y == gcd(a, b)を満たす x, y を見つける
 * @return gcd(a, b)
 * x が a の逆元に相当
 */
long long extended_gcd(long long a, long long b, long long &x, long long &y) {
    /*
    a * x0 + b * y0 == gcd(a, b)
    ↓ a = q * b + r（ユークリッドの互除法）
    -> b * x1 + r * y1 == gcd(a, b)
    -> ...
    -> gcd(a, b) * xn + 0 * yn == gcd(a, b)
    */
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long prev_x, prev_y;
    long long gcd = extended_gcd(b, a % b, prev_x, prev_y);
    // 帰りがけに係数を更新
    x = prev_y;
    y = prev_x - (a / b) * prev_y;
    
    return gcd;
}

#endif

#line 1 "Math/extended_gcd.hpp"



/**
 * @brief a * x + b * y == gcd(a, b)を満たす x, y を見つける
 * @return gcd(a, b)
 * x が a の逆元に相当
 */
long long extended_gcd(long long a, long long b, long long &x, long long &y) {
    /*
    a * x0 + b * y0 == gcd(a, b)
    ↓ a = q * b + r（ユークリッドの互除法）
    -> b * x1 + r * y1 == gcd(a, b)
    -> ...
    -> gcd(a, b) * xn + 0 * yn == gcd(a, b)
    */
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long prev_x, prev_y;
    long long gcd = extended_gcd(b, a % b, prev_x, prev_y);
    // 帰りがけに係数を更新
    x = prev_y;
    y = prev_x - (a / b) * prev_y;
    
    return gcd;
}

Back to top page