提出 #46411797

---

ソースコード 拡げる

#include <bits/stdc++.h>

using i64 = long long;

int phi(int n) {
    int res = n;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            while (n % i == 0) {
                n /= i;
            }
            res = res / i * (i - 1);
        }
    }
    if (n > 1) {
        res = res / n * (n - 1);
    }
    return res;
}

int power(int a, i64 b, int p) {
    int res = 1;
    for (; b; b /= 2, a = 1LL * a * a % p) {
        if (b % 2) {
            res = 1LL * res * a % p;
        }
    }
    return res;
}

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

i64 get(int a, int m) {
    if (m == 1) {
        return 1E9;
    }
    int p = phi(m);
    int x, y;
    int g = exgcd(m, p, x, y);
    i64 u = get(a, g);
    int v = (power(a, u, m) - u) % m;
    if (v < 0) {
        v += m;
    }
    i64 res = 1LL * (v / g) * y % (m / g);
    if (res < 0) {
        res += m / g;
    }
    u += res * p;
    return u;
}

void solve() {
    int a, m;
    std::cin >> a >> m;
    
    std::cout << get(a, m) << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}

提出情報

ジャッジ結果