nt/discrete_log.hpp

View this file on GitHub
Last update: 2023-11-21 19:08:32+09:00
Include: #include "nt/discrete_log.hpp"

Depends on

Required by

mod/mod_log.hpp

Verified with

Code

#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, int MP_SIZE = 20>
ll discrete_log_acted(typename ActedSet::A x, typename ActedSet::S s,
                      typename ActedSet::S t, F H, ll lb, ll ub) {
  static HashMap<bool, MP_SIZE, true> MP;
  MP.reset();
  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;

  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, int LOG = 20, bool KEEP_IDS = false>
struct HashMap {
  static constexpr int N = (1 << LOG);
  u64* key;
  Val* val;
  vc<int> IDS;
  bitset<N> used;
  const int shift;
  const u64 r = 11995408973635179863ULL;
  HashMap() : key(new u64[N]), val(new Val[N]), shift(64 - LOG) {}
  u32 hash(u64 x) {
    static const u64 FIXED_RANDOM
        = std::chrono::steady_clock::now().time_since_epoch().count();
    return (u64(x + FIXED_RANDOM) * r) >> shift;
  }

  int index(const u64& k) {
    int i = 0;
    for (i = hash(k); used[i] && key[i] != k; (i += 1) &= (N - 1)) {}
    return i;
  }

  Val& operator[](const u64& k) {
    int i = index(k);
    if (!used[i]) {
      used[i] = 1, key[i] = k, val[i] = Val{};
      if constexpr (KEEP_IDS) IDS.eb(i);
    }
    return val[i];
  }

  Val get(const u64& k, Val default_value) {
    int i = index(k);
    if (!used[i]) return default_value;
    return val[i];
  }

  bool count(const u64& k) {
    int i = index(k);
    return used[i] && key[i] == k;
  }

  void reset() {
    static_assert(KEEP_IDS);
    for (auto&& i: IDS) used[i] = 0;
    IDS.clear();
  }

  // f(key, val)

  template <typename F>
  void enumerate_all(F f) {
    static_assert(KEEP_IDS);
    for (auto&& i: IDS) f(key[i], val[i]);
  }
};
#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, int MP_SIZE = 20>
ll discrete_log_acted(typename ActedSet::A x, typename ActedSet::S s,
                      typename ActedSet::S t, F H, ll lb, ll ub) {
  static HashMap<bool, MP_SIZE, true> MP;
  MP.reset();
  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;

  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);
}