Fu_L's Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub Fu-L/cp-library

:heavy_check_mark: verify/unit_test/math/log_mod.test.cpp

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#include "../../../src/template/template.hpp"
#include "../../../src/math/log_mod.hpp"
ll brute(ll a, ll b, ll mod) {
    a %= mod;
    b %= mod;
    if(a < 0) a += mod;
    if(b < 0) b += mod;
    ll cur = 1 % mod;
    rep(k, 0, 100) {
        if(cur == b) return k;
        cur = cur * a % mod;
    }
    return -1;
}
int main() {
    rep(mod, 1, 50) {
        rep(a, -50, 50) {
            rep(b, -50, 50) {
                assert(log_mod(a, b, mod) == brute(a, b, mod));
            }
        }
    }
    int a, b;
    cin >> a >> b;
    cout << a + b << '\n';
}
#line 1 "verify/unit_test/math/log_mod.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
#line 4 "src/template/template.hpp"
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 2 "src/template/policy_based_data_structure.hpp"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
using namespace __gnu_pbds;
#line 4 "src/math/log_mod.hpp"
long long log_mod(long long a, long long b, const long long mod) {
    assert(mod >= 1);
    a %= mod;
    b %= mod;
    if(a < 0) a += mod;
    if(b < 0) b += mod;
    if(mod == 1) return 0;
    long long g = 1;
    for(long long i = mod; i; i /= 2) (g *= a) %= mod;
    g = gcd(g, mod);
    long long t = 1, c = 0;
    for(; t % g; ++c) {
        if(t == b) return c;
        (t *= a) %= mod;
    }
    if(b % g) return -1;
    t /= g;
    b /= g;
    const long long n = mod / g;
    long long h = 0, gs = 1;
    for(; h * h < n; ++h) (gs *= a) %= n;
    gp_hash_table<long long, long long> ht;
    for(long long s = 0, e = b; s < h; ht[e] = ++s) {
        (e *= a) %= n;
    }
    for(long long s = 0, e = t; s < n;) {
        (e *= gs) %= n;
        s += h;
        if(ht.find(e) != ht.end()) return c + s - ht[e];
    }
    return -1;
}
#line 4 "verify/unit_test/math/log_mod.test.cpp"
ll brute(ll a, ll b, ll mod) {
    a %= mod;
    b %= mod;
    if(a < 0) a += mod;
    if(b < 0) b += mod;
    ll cur = 1 % mod;
    rep(k, 0, 100) {
        if(cur == b) return k;
        cur = cur * a % mod;
    }
    return -1;
}
int main() {
    rep(mod, 1, 50) {
        rep(a, -50, 50) {
            rep(b, -50, 50) {
                assert(log_mod(a, b, mod) == brute(a, b, mod));
            }
        }
    }
    int a, b;
    cin >> a >> b;
    cout << a + b << '\n';
}
Back to top page