solve.cpp

#include <bits/extc++.h>

using namespace std;
using ll = long long;

using LLL = __int128;

ll modpow(ll e, ll p, ll m) {
    ll r = 1;
    while(p) {
        if(p & 1) r = (LLL)r * e % m;
        e = (LLL) e * e % m;
        p >>= 1;
    }
    return r;
}

ll modmul(ll a, ll b, ll m) {
    return (LLL) a * b % m;
}

struct Factorization {
    struct MillerRabin {
        // n < 4759123141     chk = [2, 7, 61]
        // n < 1122004669633  chk = [2, 13, 23, 1662803]
        // n < 2^64           chk = [2, 325, 9375, 28178, 450775, 9780504, 1795265022]
        vector<long long> chk = {2,325,9375,28178,450775,9780504,1795265022};
        bool Check(long long a, long long u, long long n, int t) {
            a = modpow(a, u, n);
            if (a == 0 || a == 1 || a == n - 1) return true;
            for (int i = 0; i < t; ++i) {
                a = modmul(a, a, n);
                if (a == 1) return false;
                if (a == n - 1) return true;
            }
            return false;
        }
        bool operator()(long long n) {
            if (n < 2) return false;
            if (n % 2 == 0) return n == 2;
            long long u = n - 1; int t = 0;
            for (; !(u & 1); u >>= 1, ++t);
            for (long long i : chk) {
                if (!Check(i, u, n, t)) return false;
            }
            return true;
        }
    } prime;
    map<long long, int> cnt;
    void pollardRho(long long n) {
        if (n == 1) return;
        if (prime(n)) return ++cnt[n], void();
        if (n % 2 == 0) return pollardRho(n / 2), ++cnt[2], void();
        long long x = 2, y = 2, d = 1, p = 1;
        auto f = [&](auto x, auto n, int p) { return (modmul(x, x, n) + p) % n; };
        while (true) {
            if (d != n && d != 1) {
                pollardRho(n / d);
                pollardRho(d);
                return;
            }
            if (d == n) ++p;
            x = f(x, n, p); y = f(f(y, n, p), n, p);
            d = __gcd(abs(x - y), n);
        }
    }
    ll mxPrime(ll n) {
        ll mx = 0;
        cnt.clear();
        pollardRho(n);
        for(auto [a, b]: cnt) mx = max(mx, a);
        return mx;
    }
} factor;


struct CRT {
    ll R, M;
    CRT() : R(0), M(1) {}
    template <typename T> tuple<T, T, T> extgcd(T a, T b) {
        if (!b) return make_tuple(a, 1, 0);
        T d, x, y;
        tie(d, x, y) = extgcd(b, a % b);
        return make_tuple(d, y, x - (a / b) * y);
    }
    void add(ll r, ll m) {
        long long d, x, y;
        tie(d, x, y) = extgcd(M, m * 1ll);
        assert ((r - R) % d == 0);
        long long new_M = M / __gcd(M, 1ll * m) * m;
        R += modmul(modmul(x, (r - R) / d, new_M), M, new_M);
        M = new_M;
        ((R %= M) += M) %= M;
    }
    pair<ll,ll> operator()() const {
        return {R, M};
    }
};

ll BSGS(ll a, ll b, ll m, ll T) {
    // a^x = b (mod m), and T is the period
    ll n = sqrt(T) + 1;

    ll an = modpow(a, n, m);

    unordered_map<ll, ll> vals;
    for (ll q = 0, cur = b; q <= n; ++q) {
        vals[cur] = q;
        cur = ((LLL) cur * a) % m;
    }
    // std::cerr << "q = " << q << '\n';

    for (ll p = 1, cur = 1; p <= n; ++p) {
        cur = ((LLL) cur * an) % m;
        if (vals.count(cur)) {
            ll ans = n * p - vals[cur];
            return ans;
        }
    }
    cerr << "a = " << a << " b = " << b << " m = " << m << " T = " << T << '\n';
    cerr << "NOT FOUND\n";
    exit(1);
}

using __gnu_cxx::power;

ll discreteLog(ll a, ll b, ll m) {
    // m is prime
    auto solve = [m](ll g, ll h, ll p, ll e) {
        ll x = 0;
        ll r = modpow(g, power(p, e-1), m);
        ll invg = modpow(g, m-2, m);
        for(int k = 0; k < e; k++) {
            ll hk = modpow(modmul(modpow(invg, x, m), h, m), power(p, e-1-k), m);
            ll d = BSGS(r, hk, m, p);
            x += power(p, k) * d;
            // cerr<<"k = "<<k<<" ; ";
        }
        // cerr << '\n';
        return x;
    };
    ll phi = m-1;
    CRT crt;
    for(auto [p, e]: factor.cnt) {
        ll P = power(p, e);
        ll X = solve(modpow(a, phi / P, m), modpow(b, phi / P, m), p, e);
        crt.add(X, P);
    }
    assert(crt().second == phi);
    assert(modpow(a, crt().first, m) == b);
    return crt().first;
}


struct Edge {
    int j;
    ll m, g, A, B;
    Edge(int j, ll m, ll g, ll A, ll B) : j(j), m(m), g(g), A(A), B(B) {}
};

signed main() {
    std::cerr << "solve.cpp::main() start.\n";
    ios_base::sync_with_stdio(0), cin.tie(0);
    const int n = 420;
    int a, b;
    vector<vector<Edge>> adj(n);
    while(cin >> a >> b) {
        assert(1 <= a && a <= n && 1 <= b && b <= n && a != b);
        ll m, g, A, B;
        cin >> m >> g >> A >> B;
        --a, --b;
        adj[a].emplace_back(b, m, g, A, B);
        adj[b].emplace_back(a, m, g, B, A);
    }
    vector<ll> ans;
    vector<int> vis(n);
    function<void(int)> dfs = [&](int i) {
        vis[i] = true;
        for(auto [j, m, g, A, B]: adj[i]) {
            if(vis[j]) continue;
            if(factor.mxPrime(m-1) >= 1e15) {
                cerr << m-1 << '\n';
                continue;
            }
            // cerr << A << ' ' << B << '\n';
            ll sa = discreteLog(g, A, m);
            ll sb = discreteLog(g, B, m);
            assert(modpow(g, sa, m) == A && modpow(g, sb, m) == B);
            ans.emplace_back(modpow(A, sb, m));
            // cerr << ans.back() << '\n';
            dfs(j);
        }
    };
    dfs(0);
    std::cerr << "ans.size() = " << ans.size() << '\n';
    assert(ans.size() == n-1);
    for(ll x: ans)
        cout << x << '\n';
}