This documentation is automatically generated by online-judge-tools/verification-helper
#include "nt/discrete_log.hpp"
#include "alg/monoid/mul.hpp"
#include "alg/acted_set/from_monoid.hpp"
#include "ds/hashmap.hpp"
// モノイド X の作用する集合 S、ハッシュ関数 H:S -> Z
// x in X, s, t in S に対して x^ns = t を解く
// [lb, ub) の最初の解をかえす。なければ -1 をかえす。
template <typename ActedSet, typename F>
ll discrete_log_acted(typename ActedSet::A x, typename ActedSet::S s,
typename ActedSet::S t, F H, ll lb, ll ub) {
using Mono = typename ActedSet::Monoid_A;
using X = typename Mono::value_type;
using S = typename ActedSet::S;
if (lb >= ub) return -1;
auto xpow = [&](ll n) -> X {
X p = x;
X res = Mono::unit();
while (n) {
if (n & 1) res = Mono::op(res, p);
p = Mono::op(p, p);
n /= 2;
}
return res;
};
auto Ht = H(t);
s = ActedSet::act(s, xpow(lb));
u64 LIM = ub - lb;
ll K = sqrt(LIM) + 1;
HashMap<char> MP(K);
FOR(k, K) {
t = ActedSet::act(t, x);
MP[H(t)] = 1;
}
X y = xpow(K);
int failed = 0;
FOR(k, K + 1) {
S s1 = ActedSet::act(s, y);
if (MP.count(H(s1))) {
FOR(i, K) {
if (H(s) == Ht) {
ll ans = k * K + i + lb;
return (ans >= ub ? -1 : ans);
}
s = ActedSet::act(s, x);
}
if (failed) return -1;
failed = 1;
}
s = s1;
}
return -1;
}
// 群 X における log_a b の計算
// ハッシュ関数 H : X -> long long を持たせる
// [lb, ub) の最初の解をかえす、なければ -1
template <typename Monoid, typename F>
ll discrete_log_monoid(typename Monoid::X a, typename Monoid::X b, F H, ll lb,
ll ub) {
using AM = ActedSet_From_Monoid<Monoid>;
return discrete_log_acted<AM>(a, Monoid::unit(), b, H, lb, ub);
}
#line 2 "alg/monoid/mul.hpp"
template <class T>
struct Monoid_Mul {
using value_type = T;
using X = T;
static constexpr X op(const X &x, const X &y) noexcept { return x * y; }
static constexpr X inverse(const X &x) noexcept { return X(1) / x; }
static constexpr X unit() { return X(1); }
static constexpr bool commute = true;
};
#line 1 "alg/acted_set/from_monoid.hpp"
template <typename Monoid>
struct ActedSet_From_Monoid {
using Monoid_A = Monoid;
using A = typename Monoid::value_type;
using S = A;
static S act(const S &x, const A &g) { return Monoid::op(x, g); }
};
#line 2 "ds/hashmap.hpp"
// u64 -> Val
template <typename Val>
struct HashMap {
// n は入れたいものの個数で ok
HashMap(u32 n = 0) { build(n); }
void build(u32 n) {
u32 k = 8;
while (k < n * 2) k *= 2;
cap = k / 2, mask = k - 1;
key.resize(k), val.resize(k), used.assign(k, 0);
}
// size を保ったまま. size=0 にするときは build すること.
void clear() {
used.assign(len(used), 0);
cap = (mask + 1) / 2;
}
int size() { return len(used) / 2 - cap; }
int index(const u64& k) {
int i = 0;
for (i = hash(k); used[i] && key[i] != k; i = (i + 1) & mask) {}
return i;
}
Val& operator[](const u64& k) {
if (cap == 0) extend();
int i = index(k);
if (!used[i]) { used[i] = 1, key[i] = k, val[i] = Val{}, --cap; }
return val[i];
}
Val get(const u64& k, Val default_value) {
int i = index(k);
return (used[i] ? val[i] : default_value);
}
bool count(const u64& k) {
int i = index(k);
return used[i] && key[i] == k;
}
// f(key, val)
template <typename F>
void enumerate_all(F f) {
FOR(i, len(used)) if (used[i]) f(key[i], val[i]);
}
private:
u32 cap, mask;
vc<u64> key;
vc<Val> val;
vc<bool> used;
u64 hash(u64 x) {
static const u64 FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count();
x += FIXED_RANDOM;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return (x ^ (x >> 31)) & mask;
}
void extend() {
vc<pair<u64, Val>> dat;
dat.reserve(len(used) / 2 - cap);
FOR(i, len(used)) {
if (used[i]) dat.eb(key[i], val[i]);
}
build(2 * len(dat));
for (auto& [a, b]: dat) (*this)[a] = b;
}
};
#line 4 "nt/discrete_log.hpp"
// モノイド X の作用する集合 S、ハッシュ関数 H:S -> Z
// x in X, s, t in S に対して x^ns = t を解く
// [lb, ub) の最初の解をかえす。なければ -1 をかえす。
template <typename ActedSet, typename F>
ll discrete_log_acted(typename ActedSet::A x, typename ActedSet::S s,
typename ActedSet::S t, F H, ll lb, ll ub) {
using Mono = typename ActedSet::Monoid_A;
using X = typename Mono::value_type;
using S = typename ActedSet::S;
if (lb >= ub) return -1;
auto xpow = [&](ll n) -> X {
X p = x;
X res = Mono::unit();
while (n) {
if (n & 1) res = Mono::op(res, p);
p = Mono::op(p, p);
n /= 2;
}
return res;
};
auto Ht = H(t);
s = ActedSet::act(s, xpow(lb));
u64 LIM = ub - lb;
ll K = sqrt(LIM) + 1;
HashMap<char> MP(K);
FOR(k, K) {
t = ActedSet::act(t, x);
MP[H(t)] = 1;
}
X y = xpow(K);
int failed = 0;
FOR(k, K + 1) {
S s1 = ActedSet::act(s, y);
if (MP.count(H(s1))) {
FOR(i, K) {
if (H(s) == Ht) {
ll ans = k * K + i + lb;
return (ans >= ub ? -1 : ans);
}
s = ActedSet::act(s, x);
}
if (failed) return -1;
failed = 1;
}
s = s1;
}
return -1;
}
// 群 X における log_a b の計算
// ハッシュ関数 H : X -> long long を持たせる
// [lb, ub) の最初の解をかえす、なければ -1
template <typename Monoid, typename F>
ll discrete_log_monoid(typename Monoid::X a, typename Monoid::X b, F H, ll lb,
ll ub) {
using AM = ActedSet_From_Monoid<Monoid>;
return discrete_log_acted<AM>(a, Monoid::unit(), b, H, lb, ub);
}