Submission #1689412

---

Source Code Expand

#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
LL Q, A, M;

LL phi(LL x) {
    LL ret = x;
    for(LL i = 2; i * i <= x; i++)
        if (x % i == 0) {
            ret = ret * (i - 1) / i;
            while (x % i == 0) x /= i;
        }
    if (x > 1) ret = ret * (x - 1) / x;
    return ret;
}

LL Pow(LL x, LL p, LL Mo) {
    LL ret = 1;
    for(; p; p = p / 2, x = (x * x) % Mo)
        if (p & 1) ret = (ret * x) % Mo;
    return ret;
}

LL exgcd(LL a, LL b, LL &x, LL &y) {
    if (!b) {
        x = 1, y = 0;return a;
    } else {
        LL ret = exgcd(b, a % b, y, x);
        y -= x * (a / b);
        return ret;
    }
}

LL sol(LL A, LL M) {
    if (M == 1) return 1;
    LL p = phi(M), g = __gcd(M, p);
    LL x = sol(A, g);
    LL tx = x % p, Ax = Pow(A, x, M), X, Y;
    exgcd(M, -p, X, Y);
    X = (X * (tx - Ax) / g) % (p / g);
    if (X <= 0) X += (p / g);
    return Ax + X * M;
}

int main() {
    cin >> Q;
    while (Q--) {
        cin >> A >> M;
        LL K = sol(A, M);
        //cout << K << " " << (Pow(A, K, M) == K % M) << endl;
        cout << K << endl;
    }
}

Submission Info

Judge Result