Discrete Logarithm of Monoid Action
(misc/discrete_log_monoid_action.hpp)

• View this file on GitHub
• Last update: 2024-01-08 00:27:17+09:00
• Include: #include "misc/discrete_log_monoid_action.hpp"

Description

モノイド作用に関する離散対数問題を解く．すなわち，モノイド $M$ が集合 $S$ に作用しているとき，$x \in X, s,t\in S$ と正整数 $N$ に対して $x^n s = t$ かつ $0 \leq n \lt N$ となる $n$ が存在するか判定し，あればそのうち最小のものを求める．

Operations

• int discrete_log_monoid_action(T x, S s, S t, long long N)
  • $x^n s=t$ かつ $0 \leq n \lt N$ となる $n$ が存在すればそのうち最小のものを，存在しなければ $-1$ を返す
  • 時間計算量: $\mathrm{expected}\,O(\sqrt{N})$

Note

集合 S は std::hash を実装している必要がある．

Reference

• モノイド作用に関する離散対数問題
• verify: https://atcoder.jp/contests/abc270/submissions/40150377

Code

#pragma once
#include <cmath>
#include <unordered_set>

template <typename M, typename S, S (*act)(typename M::T, S)>
long long discrete_log_monoid_action(typename M::T x, S s, S t, long long N) {
    using T = M::T;

    // baby-step
    const int m = std::sqrt(N) + 1;
    std::unordered_set<S> babies;
    S baby = t;
    for (int i = 1; i <= m; ++i) {
        baby = act(x, baby);
        babies.insert(baby);
    }

    // giant-step
    T xm = M::id(), y = x;
    int m_ = m;
    while (m_) {
        if (m_ & 1) xm = M::op(xm, y);
        y = M::op(y, y);
        m_ >>= 1;
    }

    S giant = s;
    bool first = true;
    for (int i = 0; i <= N / m; ++i) {
        if (babies.contains(act(xm, giant))) {
            S u = giant;
            for (int j = 0; j < m; ++j) {
                if (u == t) {
                    return 1LL * m * i + j;
                }
                u = act(x, u);
            }
            if (!first) return -1;
            first = false;
        }
        giant = act(xm, giant);
    }
    return -1;
}

#line 2 "misc/discrete_log_monoid_action.hpp"
#include <cmath>
#include <unordered_set>

template <typename M, typename S, S (*act)(typename M::T, S)>
long long discrete_log_monoid_action(typename M::T x, S s, S t, long long N) {
    using T = M::T;

    // baby-step
    const int m = std::sqrt(N) + 1;
    std::unordered_set<S> babies;
    S baby = t;
    for (int i = 1; i <= m; ++i) {
        baby = act(x, baby);
        babies.insert(baby);
    }

    // giant-step
    T xm = M::id(), y = x;
    int m_ = m;
    while (m_) {
        if (m_ & 1) xm = M::op(xm, y);
        y = M::op(y, y);
        m_ >>= 1;
    }

    S giant = s;
    bool first = true;
    for (int i = 0; i <= N / m; ++i) {
        if (babies.contains(act(xm, giant))) {
            S u = giant;
            for (int j = 0; j < m; ++j) {
                if (u == t) {
                    return 1LL * m * i + j;
                }
                u = act(x, u);
            }
            if (!first) return -1;
            first = false;
        }
        giant = act(xm, giant);
    }
    return -1;
}

Back to top page