test/power_tower.test.cpp

• View this file on GitHub
• Last update: 2022-12-02 10:32:05+00:00
• Problem: https://yukicoder.me/problems/no/181

Depends on

• Power tower (math/power_tower.hpp)

Code

#define PROBLEM "https://yukicoder.me/problems/no/181"

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

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int A, N, M;
    std::cin >> A >> N >> M;
    std::vector<int> a(std::min(N, 24), A);
    std::cout << power_tower(a, M) << '\n';
}

#line 1 "test/power_tower.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/181"

#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/power_tower.test.cpp"
#include <bits/stdc++.h>

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int A, N, M;
    std::cin >> A >> N >> M;
    std::vector<int> a(std::min(N, 24), A);
    std::cout << power_tower(a, M) << '\n';
}

Back to top page