lib/extgcd.hpp

• View this file on GitHub
• Last update: 2020-05-10 11:45:22+09:00
• Include: #include "lib/extgcd.hpp"

Required by

• lib/chinese_remainder_theorem.hpp

Verified with

• test/chinese_remainder_theorem.yuki.447.test.cpp
• test/extgcd.aoj.NTL_1_E.test.cpp

Code

#ifndef CPLIB_LIB_EXTGCD_H_
#define CPLIB_LIB_EXTGCD_H_

#include <tuple>
#include <utility>

// Find x and y such that a*x + b*y = gcd(a, b)
// Return gcd(a, b)
long long extgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    long long ret = extgcd(b, a%b, x, y);
    std::tie(x, y) = std::make_pair(y, x - a / b * y);
    return ret;
}

#endif  // CPLIB_LIB_EXTGCD_H_

#line 1 "lib/extgcd.hpp"



#include <tuple>
#include <utility>

// Find x and y such that a*x + b*y = gcd(a, b)
// Return gcd(a, b)
long long extgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    long long ret = extgcd(b, a%b, x, y);
    std::tie(x, y) = std::make_pair(y, x - a / b * y);
    return ret;
}

Back to top page