C++ Library for Competitive Programming
/*
* @title 数学/離散対数問題
*
* verification-helper: PROBLEM https://judge.yosupo.jp/problem/discrete_logarithm_mod
*/
#include <iostream>
#include "emthrm/math/mod_log.hpp"
int main() {
int t;
std::cin >> t;
while (t--) {
int x, y, m;
std::cin >> x >> y >> m;
std::cout << emthrm::mod_log(x, y, m) << '\n';
}
return 0;
}
#line 1 "test/math/mod_log.test.cpp"
/*
* @title 数学/離散対数問題
*
* verification-helper: PROBLEM https://judge.yosupo.jp/problem/discrete_logarithm_mod
*/
#include <iostream>
#line 1 "include/emthrm/math/mod_log.hpp"
#include <map>
#line 1 "include/emthrm/math/mod_pow.hpp"
namespace emthrm {
long long mod_pow(long long x, long long n, const int m) {
if ((x %= m) < 0) x += m;
long long res = 1;
for (; n > 0; n >>= 1) {
if (n & 1) res = (res * x) % m;
x = (x * x) % m;
}
return res;
}
} // namespace emthrm
#line 7 "include/emthrm/math/mod_log.hpp"
namespace emthrm {
int mod_log(long long g, long long y, const int m) {
if (m == 1) [[unlikely]] return 0;
if ((g %= m) < 0) g += m;
if ((y %= m) < 0) y += m;
if (g == 0) [[unlikely]] {
if (y == 1) return 0;
if (y == 0) return 1;
return -1;
}
int root = 1;
while (root * root < m) ++root;
std::map<long long, int> baby;
long long p = 1;
for (int i = 0; i < root; ++i) {
if (p == y) return i;
baby[p * y % m] = i;
p = (p * g) % m;
}
long long brute_force = p;
for (int i = root; i < 100; ++i) {
if (i == m) return -1;
if (brute_force == y) return i;
brute_force = (brute_force * g) % m;
}
long long giant = p;
for (int i = 1; i <= root; ++i) {
if (const auto it = baby.find(giant); it != baby.end()) {
const int ans = static_cast<long long>(i) * root - it->second;
if (mod_pow(g, ans, m) == y) return ans;
}
giant = (giant * p) % m;
}
return -1;
}
} // namespace emthrm
#line 10 "test/math/mod_log.test.cpp"
int main() {
int t;
std::cin >> t;
while (t--) {
int x, y, m;
std::cin >> x >> y >> m;
std::cout << emthrm::mod_log(x, y, m) << '\n';
}
return 0;
}