test/tetration_mod.test.cpp

• View this file on GitHub
• Last update: 2022-12-02 10:32:05+00:00
• Problem: https://judge.yosupo.jp/problem/tetration_mod

Depends on

• Power tower (math/power_tower.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/tetration_mod"

#include "math/power_tower.hpp"
#include <bits/stdc++.h>

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int T;
    std::cin >> T;
    for (auto i = 0; i < T; ++i) {
        int A, B, M;
        std::cin >> A >> B >> M;
        if (A == 0) {
            std::cout << ((B & 1) ^ 1) % M;
        } else {
            const auto n = std::min(B, 64);
            std::vector<int> a(n, A);
            std::cout << power_tower(a, M);
        }
        std::cout << '\n';
    }
}

#line 1 "test/tetration_mod.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/tetration_mod"

#line 1 "math/power_tower.hpp"



#include <cassert>
#include <limits>
#include <type_traits>
#include <vector>

template <typename T> T euler_phi(T n) {
    T phi = n;
    for (T i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            phi -= phi / i;
            while (n % i == 0) {
                n /= i;
            }
        }
    }
    if (n != 1) {
        phi -= phi / n;
    }
    return phi;
}

template <typename T, typename Promote = unsigned long long>
T power_tower(const std::vector<T> &a, T m) {
    static_assert(std::is_integral_v<T>);
    assert(m > 0);
    std::vector<unsigned long long> mod_chain{
        static_cast<unsigned long long>(m)};
    while (mod_chain.back() > 1) {
        const auto phi = euler_phi(mod_chain.back());
        mod_chain.push_back(phi);
    }
    const auto f = [](Promote x, Promote n, Promote mod) {
        Promote r = 1;
        if (x > mod) {
            x = x % mod + mod;
        }
        while (n) {
            if (n & 1) {
                r *= x;
                if (r > mod) {
                    r = r % mod + mod;
                }
            }
            x *= x;
            if (x > mod) {
                x = x % mod + mod;
            }
            n >>= 1;
        }
        return r;
    };
    Promote r = 1;
    const auto k = static_cast<int>(std::min(a.size(), mod_chain.size()));
    for (auto i = k - 1; i >= 0; --i) {
        assert(a[i] > 0);
        r = f(static_cast<Promote>(a[i]), r, mod_chain[i]);
    }
    return static_cast<T>(r % static_cast<Promote>(m));
}


#line 4 "test/tetration_mod.test.cpp"
#include <bits/stdc++.h>

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int T;
    std::cin >> T;
    for (auto i = 0; i < T; ++i) {
        int A, B, M;
        std::cin >> A >> B >> M;
        if (A == 0) {
            std::cout << ((B & 1) ^ 1) % M;
        } else {
            const auto n = std::min(B, 64);
            std::vector<int> a(n, A);
            std::cout << power_tower(a, M);
        }
        std::cout << '\n';
    }
}

Back to top page