test/tetration.test.cpp

View this file on GitHub
Last update: 2025-06-11 17:30:11+09:00
Problem: https://judge.yosupo.jp/problem/tetration_mod

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/tetration_mod"
#include <iostream>
#include "C++/math/tetration.hpp"
void solve() {
    int64_t a, b, m;
    std::cin >> a >> b >> m;
    std::cout << man::tetration(a, b, m) << '\n';
}
int main() {
    int t;
    std::cin >> t;
    while(t--) {
        solve();
    }
}

#line 1 "test/tetration.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/tetration_mod"
#include <iostream>
#line 2 "C++/math/tetration.hpp"

#line 2 "C++/math/euler_phi.hpp"
namespace man {
template <std::integral T> constexpr inline T euler_phi(T n) noexcept {
	T ret = n;
	for(T i = 2; i * i <= n; ++i) {
	    if(n % i == 0) {
			ret -= ret / i;
			while(n % i == 0) {
				n /= i;
			}
		}
	}
	if(n > 1) {
		ret -= ret / n;
	}
	return ret;
}
}

/**
 * @brief Euler's Phi-function
 */
#line 4 "C++/math/tetration.hpp"
#ifndef TEMPLATE
namespace man {
template <std::integral T> constexpr inline T pow(T a, T b, const T mod = 0) noexcept {
	T ret = 1;
	if(mod != 0) {
		ret %= mod;
		a %= mod;
	}
	while(b > 0) {
		if(b & 1) {
			ret *= a;
		}
		if(mod != 0) {
			ret %= mod;
		}
		a *= a;
		if(mod) {
			a %= mod;
		}
		b >>= 1;
	}
	return ret;
}
}
#endif
namespace man {
template <std::integral T> constexpr inline T tetration(const T a, const T b, const T m) noexcept {
    if(m == 1) {
        return 0;
    }
    if(a == 0) {
        return (b & 1) ? 0 : 1;
    }
    if(b == 0) {
        return 1;
    }
    if(b == 1) {
        return a % m;
    }
    if(b == 2) {
        return pow(a, a, m);
    }
    const auto phi = euler_phi(m);
    auto tmp = tetration(a, b - 1, phi);
    if(!tmp) {
        tmp += phi;
    }
    return pow(a, tmp, m);
}
}

/**
 * @brief Tetration(a↑↑b)
 */
#line 4 "test/tetration.test.cpp"
void solve() {
    int64_t a, b, m;
    std::cin >> a >> b >> m;
    std::cout << man::tetration(a, b, m) << '\n';
}
int main() {
    int t;
    std::cin >> t;
    while(t--) {
        solve();
    }
}