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

• View this file on GitHub
• Last update: 2022-12-30 22:29:44+09:00
• Include: #include "math/extend-gcd.hpp"
• Link: View error logs on GitHub Actions

Verified with

• verify/AOJ-NTL_1_E.test.cpp

Code

template< typename T >
T extendGCD(T a, T b, T &x, T &y){
  T d = a;
  if(b != 0){
    auto t = extendGCD(b, a % b, y, x);
    d = t;
    y -= (a / b) * x;
  }else{
    x = 1;
    y = 0;
  }
  return d;
}

#line 1 "math/extend-gcd.hpp"
template< typename T >
T extendGCD(T a, T b, T &x, T &y){
  T d = a;
  if(b != 0){
    auto t = extendGCD(b, a % b, y, x);
    d = t;
    y -= (a / b) * x;
  }else{
    x = 1;
    y = 0;
  }
  return d;
}

Back to top page