cpp/math/expansion-gcd.cpp

• View this file on GitHub
• Last update: 2024-01-29 16:29:11+09:00

Required by

• cpp/geometry/two-points-distance.cpp

Verified with

• cpp/z_test/aoj-NTL_1_E.test.cpp

Code

template <typename T>
pair<T,T> extgcd(T a,T b){
  if(b!=0){
    auto A = extgcd(b,a%b);
    T tmp = A.second;
    A.second = A.first-(a/b)*A.second;
    A.first = tmp;
    return A;
  }else{
    return {1,0};
  }
}

#line 1 "cpp/math/expansion-gcd.cpp"
template <typename T>
pair<T,T> extgcd(T a,T b){
  if(b!=0){
    auto A = extgcd(b,a%b);
    T tmp = A.second;
    A.second = A.first-(a/b)*A.second;
    A.first = tmp;
    return A;
  }else{
    return {1,0};
  }
}

Back to top page