math/inv_gcd.hpp

• View this file on GitHub
• Last update: 2025-01-05 04:43:56+09:00
• Include: #include "math/inv_gcd.hpp"

Verified with

• verify/aoj/aoj_ntl_1_e.test.cpp

Code

#ifndef KK2_MATH_INV_GCD_HPP
#define KK2_MATH_INV_GCD_HPP 1

#include <algorithm>
#include <utility>

namespace kk2 {

// return {gcd(a, b), x} where a * x + b * y = gcd(a, b)
std::pair<long long, long long> inv_gcd(long long a, long long b) {
    a = a % b;
    if (a == 0) return {b, 0};
    long long s = b, t = a;
    long long m0 = 0, m1 = 1;

    while (t) {
        long long u = s / t;
        std::swap(s -= t * u, t);
        std::swap(m0 -= u * m1, m1);
    }
    if (m0 < 0) m0 += b / s;
    return {s, m0};
}

} // namespace kk2

#endif // KK2_MATH_INV_GCD_HPP

#line 1 "math/inv_gcd.hpp"



#include <algorithm>
#include <utility>

namespace kk2 {

// return {gcd(a, b), x} where a * x + b * y = gcd(a, b)
std::pair<long long, long long> inv_gcd(long long a, long long b) {
    a = a % b;
    if (a == 0) return {b, 0};
    long long s = b, t = a;
    long long m0 = 0, m1 = 1;

    while (t) {
        long long u = s / t;
        std::swap(s -= t * u, t);
        std::swap(m0 -= u * m1, m1);
    }
    if (m0 < 0) m0 += b / s;
    return {s, m0};
}

} // namespace kk2

Back to top page