test/src/number/discrete_logarithm/discrete_logarithm_mod.test.cpp

• View this file on GitHub
• Last update: 2022-09-28 21:35:14+09:00
• Problem: https://judge.yosupo.jp/problem/discrete_logarithm_mod

Depends on

• Discrete Logarithm (library/number/discrete_logarithm.hpp)

Code

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

#include <iostream>
#include <atcoder/modint>

using mint = atcoder::modint;

#include "library/number/discrete_logarithm.hpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;

    while (t --> 0) {
        int x, y, m;
        std::cin >> x >> y >> m;
        mint::set_mod(m);
        std::cout << suisen::discrete_logarithm<mint>(x, y) << '\n';
    }

    return 0;
}

#line 1 "test/src/number/discrete_logarithm/discrete_logarithm_mod.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/discrete_logarithm_mod"

#include <iostream>
#include <atcoder/modint>

using mint = atcoder::modint;

#line 1 "library/number/discrete_logarithm.hpp"



#include <cmath>
#include <unordered_map>
#include <numeric>

namespace suisen {
    namespace internal::discrete_logarithm {
        int floor_log2(int m) {
            int res = 0;
            while (1 << (res + 1) <= m) ++res;
            return res;
        }
    }

    template <typename mint>
    int discrete_logarithm_coprime(mint x, mint y) {
        const int m = mint::mod();
        if (y == 1 or m == 1) return 0;
        if (x == 0) return y == 0 ? 1 : -1;
        const int p = ::sqrt(m) + 1;
        mint a = mint(x).inv().pow(p);
        std::unordered_map<int, int> mp;
        mint pow_x = 1;
        for (int j = 0; j < p; ++j, pow_x *= x) mp.try_emplace(pow_x.val(), j);
        mint ya = y;
        for (int i = 0; i < p; ++i, ya *= a) {
            if (auto it = mp.find(ya.val()); it != mp.end()) return p * i + it->second;
        }
        return -1;
    }

    template <typename mint>
    int discrete_logarithm(mint x, mint y) {
        using namespace internal::discrete_logarithm;
        const int m = mint::mod();
        if (m == 1) return 0;
        const int d = floor_log2(m);
        mint pow_x = 1;
        for (int i = 0; i < d; ++i, pow_x *= x) if (pow_x == y) return i;
        const int g = std::gcd(pow_x.val(), m);
        if (y.val() % g) return -1;
        mint::set_mod(m / g);
        const int t = discrete_logarithm_coprime(mint(x.val()), mint(y.val()) * mint(pow_x.val()).inv());
        mint::set_mod(m);
        return t != -1 ? d + t : -1;
    }
} // namespace suisen



#line 9 "test/src/number/discrete_logarithm/discrete_logarithm_mod.test.cpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;

    while (t --> 0) {
        int x, y, m;
        std::cin >> x >> y >> m;
        mint::set_mod(m);
        std::cout << suisen::discrete_logarithm<mint>(x, y) << '\n';
    }

    return 0;
}

Back to top page