Math Enhanced
(atcoder/math_enhanced.hpp)

• View this file on GitHub
• Last update: 2021-10-25 14:39:47+09:00
• Include: #include "atcoder/math_enhanced.hpp"
• Link: https://ei1333.github.io/library/math/combinatorics/mod-log.cpp

概要

• mod_log(a, b, p) : $a^x \equiv b \bmod p$ を満たす最小の非負整数 $x$ を返す. そのような $x$ が存在しない場合は -1 を返す.
• extgcd(a, b, x, y) : $ax + by = gcd(x,y)$ を満たす $x, y$ を求め, $gcd(x, y)$ を返す.

制約

• mod_log(a, b, p) : $p$ は正整数.
• extgcd(a, b, x, y) : $a, b$ は非負整数.

計算量

• mod_log(a, b, p) : $O(\sqrt{p})$
• extgcd(a, b, x, y) : $O(\log \min(a, b))$

Verified with

• test/extgcd.test.cpp
• test/modlog.test.cpp

Code

#ifndef ATCODER_MATH_ENHANCED_HPP
#define ATCODER_MATH_ENHANCED_HPP 1

#include<numeric>
#include<ext/pb_ds/assoc_container.hpp>

namespace atcoder {

// https://ei1333.github.io/library/math/combinatorics/mod-log.cpp
int64_t mod_log(int64_t a, int64_t b, int64_t p) {
    ((a %= p) += p) %= p;
    ((b %= p) += p) %= p;
    int64_t g = 1;
    for (int64_t i = p; i; i /= 2) (g *= a) %= p;
    g = std::gcd(g, p);

    int64_t t = 1, c = 0;
    for (; t % g; c++) {
        if (t == b) return c;
        (t *= a) %= p;
    }

    if (b % g) return -1;

    t /= g;
    b /= g;
    p /= g;

    int64_t h = 0, gs = 1;

    for (; h * h < p; h++) (gs *= a) %= p;
    __gnu_pbds::gp_hash_table<int64_t, int64_t> bs;
    for (int64_t s = 0, e = b; s < h; bs[e] = ++s) {
        (e *= a) %= p;
    }

    for (int64_t s = 0, e = t; s < p;) {
        (e *= gs) %= p;
        s += h;
        if (bs.find(e) != bs.end()) return c + s - bs[e];
    }

    return -1;
}

template<class T>
T extgcd(T a, T b, T &x, T &y) {
    T d = a;
    if (b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1;
        y = 0;
    }
    return d;
}

}  // namespace atcoder

#endif  // ATCODER_MATH_ENHANCED_HPP

#line 1 "atcoder/math_enhanced.hpp"



#include<numeric>
#include<ext/pb_ds/assoc_container.hpp>

namespace atcoder {

// https://ei1333.github.io/library/math/combinatorics/mod-log.cpp
int64_t mod_log(int64_t a, int64_t b, int64_t p) {
    ((a %= p) += p) %= p;
    ((b %= p) += p) %= p;
    int64_t g = 1;
    for (int64_t i = p; i; i /= 2) (g *= a) %= p;
    g = std::gcd(g, p);

    int64_t t = 1, c = 0;
    for (; t % g; c++) {
        if (t == b) return c;
        (t *= a) %= p;
    }

    if (b % g) return -1;

    t /= g;
    b /= g;
    p /= g;

    int64_t h = 0, gs = 1;

    for (; h * h < p; h++) (gs *= a) %= p;
    __gnu_pbds::gp_hash_table<int64_t, int64_t> bs;
    for (int64_t s = 0, e = b; s < h; bs[e] = ++s) {
        (e *= a) %= p;
    }

    for (int64_t s = 0, e = t; s < p;) {
        (e *= gs) %= p;
        s += h;
        if (bs.find(e) != bs.end()) return c + s - bs[e];
    }

    return -1;
}

template<class T>
T extgcd(T a, T b, T &x, T &y) {
    T d = a;
    if (b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1;
        y = 0;
    }
    return d;
}

}  // namespace atcoder

Back to top page