test/verify/yosupo-discrete-logarithm-mod.test.cpp

• View this file on GitHub
• Last update: 2026-08-10 14:29:01+00:00
• Problem: https://judge.yosupo.jp/problem/discrete_logarithm_mod

Depends on

• Mod Log (離散対数問題) (math/combinatorics/mod-log.hpp)

Code

// clang-format off
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/discrete_logarithm_mod
// clang-format on

#include <iostream>

#include "../../math/combinatorics/mod-log.hpp"

using namespace std;

int main() {
  int T;
  cin >> T;
  while (T--) {
    long long X, Y, M;
    cin >> X >> Y >> M;
    cout << mod_log(X, Y, M) << endl;
  }
}

#line 1 "test/verify/yosupo-discrete-logarithm-mod.test.cpp"
// clang-format off
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/discrete_logarithm_mod
// clang-format on

#include <iostream>

#line 2 "math/combinatorics/mod-log.hpp"

#include <cstdint>
#include <numeric>
#include <unordered_map>

/**
 * @brief Mod Log(離散対数問題)
 *
 */
std::int64_t mod_log(std::int64_t a, std::int64_t b, std::int64_t p) {
  std::int64_t g = 1;

  for (std::int64_t i = p; i; i /= 2) (g *= a) %= p;
  g = std::gcd(g, p);

  std::int64_t t = 1, c = 0;
  for (; t % g; c++) {
    if (t == b) return c;
    (t *= a) %= p;
  }
  if (b % g) return -1;

  t /= g;
  b /= g;

  std::int64_t n = p / g, h = 0, gs = 1;

  for (; h * h < n; h++) (gs *= a) %= n;

  std::unordered_map<std::int64_t, std::int64_t> bs;
  for (std::int64_t s = 0, e = b; s < h; bs[e] = ++s) {
    (e *= a) %= n;
  }

  for (std::int64_t s = 0, e = t; s < n;) {
    (e *= gs) %= n;
    s += h;
    if (bs.count(e)) return c + s - bs[e];
  }
  return -1;
}
#line 8 "test/verify/yosupo-discrete-logarithm-mod.test.cpp"

using namespace std;

int main() {
  int T;
  cin >> T;
  while (T--) {
    long long X, Y, M;
    cin >> X >> Y >> M;
    cout << mod_log(X, Y, M) << endl;
  }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	even_mod_00	AC	145 ms	5 MB
g++	even_mod_01	AC	181 ms	5 MB
g++	even_mod_impossible_00	AC	2 ms	4 MB
g++	even_mod_impossible_01	AC	2 ms	4 MB
g++	example_00	AC	2 ms	4 MB
g++	max_random_00	AC	232 ms	5 MB
g++	max_random_01	AC	211 ms	5 MB
g++	max_random_02	AC	192 ms	5 MB
g++	max_random_yes_00	AC	216 ms	5 MB
g++	max_random_yes_01	AC	217 ms	5 MB
g++	max_random_yes_prime_00	AC	302 ms	5 MB
g++	max_random_yes_prime_01	AC	301 ms	5 MB
g++	random_00	AC	65 ms	5 MB
g++	random_01	AC	107 ms	5 MB
g++	random_02	AC	142 ms	5 MB
g++	random_prime_00	AC	324 ms	5 MB
g++	random_prime_01	AC	317 ms	5 MB
g++	small_00	AC	2 ms	4 MB
g++	small_01	AC	2 ms	3 MB
g++	small_02	AC	2 ms	4 MB
clang++	even_mod_00	AC	146 ms	5 MB
clang++	even_mod_01	AC	181 ms	5 MB
clang++	even_mod_impossible_00	AC	2 ms	4 MB
clang++	even_mod_impossible_01	AC	2 ms	4 MB
clang++	example_00	AC	2 ms	4 MB
clang++	max_random_00	AC	233 ms	5 MB
clang++	max_random_01	AC	213 ms	5 MB
clang++	max_random_02	AC	192 ms	5 MB
clang++	max_random_yes_00	AC	220 ms	5 MB
clang++	max_random_yes_01	AC	220 ms	5 MB
clang++	max_random_yes_prime_00	AC	305 ms	5 MB
clang++	max_random_yes_prime_01	AC	304 ms	5 MB
clang++	random_00	AC	65 ms	5 MB
clang++	random_01	AC	107 ms	5 MB
clang++	random_02	AC	143 ms	5 MB
clang++	random_prime_00	AC	323 ms	5 MB
clang++	random_prime_01	AC	322 ms	5 MB
clang++	small_00	AC	2 ms	4 MB
clang++	small_01	AC	2 ms	4 MB
clang++	small_02	AC	2 ms	4 MB

Back to top page