Extended Euclidean Algorithm
(math/number-theory/extgcd.hpp)

• View this file on GitHub
• Last update: 2024-01-08 17:31:43+09:00
• Include: #include "math/number-theory/extgcd.hpp"

Description

拡張 Euclid の互除法は，2変数1次不定方程式 $ax + by = \gcd(a, b)$ の解 $(x, y)$ を1組求めるアルゴリズムである．

また，これを利用して，与えられた整数 $a$ の法 $mod$ での逆元を求めることができる．Fermat の小定理を利用したアルゴリズムより制約が少なく定数倍高速であるため，基本的にこちらを用いる．

• pair<long long, long long> extgcd(long long a, long long b)
  • $ax + by = \gcd(a, b)$ の解 $(x, y)$ を1組求める
  • 時間計算量: $O(\log \min(a, b))$
• long long mod_inv(long long a, long long mod)
  • $a$ の法$mod$での逆元を求める

Required by

• Arbitrary Mod Convolution (convolution/arbitrary_mod_convolution.hpp)
• Garner's Algorithm (math/number-theory/garner.hpp)

Verified with

• test/yosupo/convolution_mod_1000000007.test.cpp

Code

#pragma once
#include <algorithm>
#include <utility>

std::pair<long long, long long> extgcd(long long a, long long b) {
    long long s = a, sx = 1, sy = 0, t = b, tx = 0, ty = 1;
    while (t) {
        long long q = s / t;
        std::swap(s -= t * q, t);
        std::swap(sx -= tx * q, tx);
        std::swap(sy -= ty * q, ty);
    }
    return {sx, sy};
}

long long mod_inv(long long a, long long mod) {
    long long inv = extgcd(a, mod).first;
    return (inv % mod + mod) % mod;
}

#line 2 "math/number-theory/extgcd.hpp"
#include <algorithm>
#include <utility>

std::pair<long long, long long> extgcd(long long a, long long b) {
    long long s = a, sx = 1, sy = 0, t = b, tx = 0, ty = 1;
    while (t) {
        long long q = s / t;
        std::swap(s -= t * q, t);
        std::swap(sx -= tx * q, tx);
        std::swap(sy -= ty * q, ty);
    }
    return {sx, sy};
}

long long mod_inv(long long a, long long mod) {
    long long inv = extgcd(a, mod).first;
    return (inv % mod + mod) % mod;
}

Back to top page