test/library_checker/number_theory/discrete_logarithm_mod.test.cpp

• View this file on GitHub
• Last update: 2024-11-04 03:12:13+09:00
• Problem: https://judge.yosupo.jp/problem/discrete_logarithm_mod

Depends on

• Baby-step giant-step (lib/math/baby-step_giant-step.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/discrete_logarithm_mod"
#include <bits/stdc++.h>
using namespace std;

#include "../../../lib/math/baby-step_giant-step.hpp"

int main(){
    int t; cin >> t;
    while(t--){
        long long x, y, m; cin >> x >> y >> m;
        cout << babyStepGiantStep(x, y, m) << "\n";
    }
}

#line 1 "test/library_checker/number_theory/discrete_logarithm_mod.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/discrete_logarithm_mod"
#include <bits/stdc++.h>
using namespace std;

#line 2 "lib/math/baby-step_giant-step.hpp"

/**
 * @brief Baby-step giant-step
 * @docs docs/math/baby-step_giant-step.md
 */

long long babyStepGiantStep(long long x, long long y, long long m){
    auto inv = [](long long a, long long m) -> long long {
        long long b = m, u = 1, v = 0;
        while(b){
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        u %= m;
        if(u < 0) u += m;
        return u;
    };

    if((x %= m) < 0) x += m;
    if((y %= m) < 0) y += m;

    long long offset, g, r = 1 % m;
    for(offset = 0; (g = gcd(x, m)) > 1; ++offset){
        if(y % g){
            if(r == y) return offset;
            return -1;
        }
        y /= g;
        m /= g;
        (r *= (x / g)) %= m;
    }

    if(m == 1) return offset;
    (y *= inv(r, m)) %= m;

    unordered_map<long long, long long> mp;
    // Baby Step
    long long z = 1, sq = sqrtl(m) + 1;
    for(int i = 0; i < sq; i++){
        mp[z] = i;
        if(mp.count(y) != 0) return offset + mp[y];
        z *= x;
        z %= m;
    }

    // Giant Step
    long long u = inv(z, m);
    for(int i = 1; i <= sq; i++){
        (y *= u) %= m;
        if(mp.count(y) != 0) return offset + mp[y] + i * sq;
    }
    return -1;
}

long long babyStepGiantStepP(long long x, long long y, long long m){
    auto inv = [](long long a, long long m) -> long long {
        long long b = m, u = 1, v = 0;
        while(b){
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        u %= m;
        if(u < 0) u += m;
        return u;
    };

    if((x %= m) < 0) x += m;
    if((y %= m) < 0) y += m;

    long long offset, g, r = 1 % m;
    for(offset = 0; (g = gcd(x, m)) > 1; ++offset){
        if(y % g && offset != 0){
            if(r == y) return offset;
            return -1;
        }
        y /= g;
        m /= g;
        (r *= (x / g)) %= m;
    }

    if(m == 1) return offset;
    (y *= inv(r, m)) %= m;

    unordered_map<long long, long long> mp;
    // Baby Step
    long long z = 1, sq = sqrtl(m) + 1;
    for(int i = 0; i < sq; i++){
        mp[z] = i;
        if(mp.count(y) != 0 && offset + mp[y]) return offset + mp[y];
        z *= x;
        z %= m;
    }

    // Giant Step
    long long u = inv(z, m);
    for(int i = 1; i <= sq; i++){
        (y *= u) %= m;
        if(mp.count(y) != 0) return offset + mp[y] + i * sq;
    }
    return -1;
}
#line 6 "test/library_checker/number_theory/discrete_logarithm_mod.test.cpp"

int main(){
    int t; cin >> t;
    while(t--){
        long long x, y, m; cin >> x >> y >> m;
        cout << babyStepGiantStep(x, y, m) << "\n";
    }
}

Back to top page