math/extgcd.hpp

• View this file on GitHub
• Last update: 2023-03-13 22:17:07+09:00
• Include: #include "math/extgcd.hpp"

Verified with

• test/aoj/NTL/NTL_1_E.test.cpp

Code

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

#line 1 "math/extgcd.hpp"
ll ext_gcd(ll a, ll b, ll &x, ll &y){
  ll d = a;
  if(b){
    d = ext_gcd(b, a % b, y, x);
    y -= (a / b) * x;
  }else{ x = 1; y = 0; }
  return d;
}

Back to top page