Discrete Logarithm of Monoid Action
(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
Code
Back to top page