Test/Math/BabyStepGiantStep.test.cpp

View this file on GitHub
Last update: 2025-01-09 01:07:21+09:00
Problem: https://judge.yosupo.jp/problem/discrete_logarithm_mod

Depends on

Library/Math/BabyStepGiantStep.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/discrete_logarithm_mod"

#include <iostream>

#include <ranges>


// begin:tag includes

#include "../../Library/Math/BabyStepGiantStep.hpp"

// end:tag includes


using ll = long long;

signed main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(0);

  int t;
  std::cin >> t;
  for ([[maybe_unused]] auto _ : std::views::iota(0, t)) {
    ll x, y, m;
    std::cin >> x >> y >> m;

    auto ans = (m == 1)
                   ? 0
                   : mtd::baby_step_giant_step<std::hash<ll>>(
                         x, ll(1), y, m - 1,
                         [&](ll _x, ll _y) { return (_x * _y) % m; },
                         [&](const ll _m, ll _x) { return (_m * _x) % m; });

    if (ans) {
      std::cout << ans.value() << std::endl;
    } else {
      std::cout << -1 << std::endl;
    }
  }
}

#line 1 "Test/Math/BabyStepGiantStep.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/discrete_logarithm_mod"

#include <iostream>

#include <ranges>


// begin:tag includes

#line 2 "Library/Math/BabyStepGiantStep.hpp"

#include <cmath>
#include <optional>
#line 6 "Library/Math/BabyStepGiantStep.hpp"
#include <unordered_set>

namespace mtd {
  /*
   * x^i * s = t (0 <= i < n) を満たす最小のi
   * O(sqrt(n))
   */
  template <class Hash, class Monoid, class T, class Product, class Op>
  std::optional<long long> baby_step_giant_step(const Monoid& x, const T& s,
                                                const T& t, long long n,
                                                const Product prod,
                                                const Op& op) {
    if (n == 0) { return (s == t) ? std::make_optional(0) : std::nullopt; }
    if (n == 1) {
      return (s == t)          ? std::make_optional(0)
             : (op(x, s) == t) ? std::make_optional(1)
                               : std::nullopt;
    }

    auto m = static_cast<long long>(std::sqrt(n));
    std::unordered_set<T, Hash> mp;
    auto xm = x;
    for (auto i : std::views::iota(0, m)) {
      mp.emplace(op(xm, t));
      if (i < m - 1) { xm = prod(xm, x); }
    }

    bool find = false;
    auto xks = s;
    for (auto k : std::views::iota(1, n / m + 5)) {
      auto next = op(xm, xks);
      if (mp.contains(next)) {
        auto xi = xks;
        for (auto i : std::views::iota(m * (k - 1), m * k + 1)) {
          if (xi == t) { return i; }
          xi = op(x, xi);
        }
        if (find) { return std::nullopt; }
        find = true;
      }
      std::swap(xks, next);
    }
    return std::nullopt;
  }
};  // namespace mtd
#line 8 "Test/Math/BabyStepGiantStep.test.cpp"
// end:tag includes


using ll = long long;

signed main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(0);

  int t;
  std::cin >> t;
  for ([[maybe_unused]] auto _ : std::views::iota(0, t)) {
    ll x, y, m;
    std::cin >> x >> y >> m;

    auto ans = (m == 1)
                   ? 0
                   : mtd::baby_step_giant_step<std::hash<ll>>(
                         x, ll(1), y, m - 1,
                         [&](ll _x, ll _y) { return (_x * _y) % m; },
                         [&](const ll _m, ll _x) { return (_m * _x) % m; });

    if (ans) {
      std::cout << ans.value() << std::endl;
    } else {
      std::cout << -1 << std::endl;
    }
  }
}