inv_gcd
(src/math/inv_gcd.hpp)

• View this file on GitHub
• Last update: 2024-11-09 02:03:28+09:00
• Include: #include "src/math/inv_gcd.hpp"

inv_gcd

pair<ll, ll> inv_gcd(ll a, ll m)

$\mathrm{gcd} (a, m)$ と $a^{-1} \pmod{m}$ を返します．

$\mathrm{gcd} (a, m) = 1$ でない場合，動作はしますが逆元は (存在しないので) 正しく計算できていないことに注意してください．

制約

• $0 \leq a$
• $1 \leq m$

計算量

• $O(\log m)$

Depends on

• template (src/template/template.hpp)

Required by

• chinese_remainder_theorem (src/math/chinese_remainder_theorem.hpp)

Verified with

• verify/yukicoder/186.test.cpp

Code

#pragma once
#include "../template/template.hpp"
constexpr pair<long long, long long> inv_gcd(long long a, const long long b) {
    a %= b;
    if(a < 0) a += b;
    if(a == 0) return {b, 0};
    long long s = b, t = a, m0 = 0, m1 = 1;
    while(t) {
        const long long u = s / t;
        s -= t * u;
        m0 -= m1 * u;
        long long tmp = s;
        s = t;
        t = tmp;
        tmp = m0;
        m0 = m1;
        m1 = tmp;
    }
    if(m0 < 0) m0 += b / s;
    return {s, m0};
}

#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/math/inv_gcd.hpp"
constexpr pair<long long, long long> inv_gcd(long long a, const long long b) {
    a %= b;
    if(a < 0) a += b;
    if(a == 0) return {b, 0};
    long long s = b, t = a, m0 = 0, m1 = 1;
    while(t) {
        const long long u = s / t;
        s -= t * u;
        m0 -= m1 * u;
        long long tmp = s;
        s = t;
        t = tmp;
        tmp = m0;
        m0 = m1;
        m1 = tmp;
    }
    if(m0 < 0) m0 += b / s;
    return {s, m0};
}

Back to top page