TIOJ 1324：指數之謎 Exponent

TIOJ 1324：指數之謎 Exponent

題目大意：問 $a_1^{a_2^{a_3^{ ^{.^{.^{.}}}}}} \text{mod}\ k$。

解法：首先對於 $gcd(a,m) = 1$，當然可以算 $a^{t\%phi(m)}\%m$，但是如果 $gcd(a,m) > 1$，就不能用歐拉定理，但還是可以觀察到會循環，只是會先經過一些非循環節的數字才開始循環，可以找出循環節數字與 $m$ 的 $gcd = g$，那在 $mod\ \frac{m}{g}$ 下 $phi[\frac{m}{g}]$ 一定可以當作循環節的長度，假設從 $a^0$ 開始，最後 $(a^N\%m) \times (a ^ {(t-N)\%phi[\frac{m}{g}]} \% \frac{m}{g}]) \%m$ 就是答案。如果 $t<N$，就直接暴力算。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int MAX = 1e6;
const int SIZE = 5e5 + 5;

bool isp[MAX + 5];
int phi[MAX + 5];
vector<int> prime;

void sieve() {
    isp[1] = phi[1] = 1;
    FOR (i, 2, MAX) {
        if (!isp[i]) {
            prime.pb (i);
            phi[i] = i - 1;
        }
        for (int p : prime) {
            int t = i * p;
            if (t > MAX)
                break;
            isp[t] = 1;
            if (i % p == 0) {
                phi[t] = phi[i] * p;
                break;
            } else
                phi[t] = phi[i] * (p - 1);
        }
    }
}

int n, k, a[SIZE];

int power (int d, int up, int mod) {
    int ans = 1;
    while (up) {
        if (up & 1)
            ans = ans * d % mod;
        d = d * d % mod;
        up >>= 1;
    }
    return ans;
}

tuple<int, int, int> len (int x, int mod) {
    int last = 1, now;
    for (int i = 1;; i++) {
        now = last * x % mod;
        if (__gcd (now, mod) == __gcd (last, mod))
            return {__gcd (now, mod), last, i - 1};
        last = now;
    }
}

int brute (int i) {
    if (i == n)
        return a[i];
    return power (a[i], brute (i + 1), 2e9);
}

bool smaller (int i, double x) {
    if (x < 1)
        return 0;
    if (i == n)
        return a[i] < x;
    return smaller (i + 1, log (x) / log (a[i]));
}

int turn (int x, int mod) {
    x %= mod;
    return x < 0 ? x + mod : x;
}

int cal (int i, int mod) {
    int f;
    if (mod == 1)
        return 0;
    if (i == n)
        return a[i] % mod;
    if (__gcd (a[i], mod) == 1)
        return power (a[i], cal (i + 1, phi[mod]), mod);
    auto [g, K, N] = len (a[i], mod);
    if (smaller (i + 1, N))
        return power (a[i], brute (i + 1), mod);
    return K * power (a[i], turn (cal (i + 1, phi[mod / g]) - N, phi[mod / g]), mod / g) % mod;
}

void solve() {
    FOR (i, 1, n) cin >> a[i];
    cin >> k;
    cout << cal (1, k) << '\n';
}

int32_t main() {
    ios::sync_with_stdio (false), cin.tie (0);
    sieve();
    while (cin >> n && n)
        solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！