Submit Info #58037

Problem Lang User Status Time Memory
Tetration Mod cpp NicholasPatrick AC 17 ms 0.46 MiB

ケース詳細
Name Status Time Memory
2_3_32_00 AC 1 ms 0.45 MiB
example_00 AC 1 ms 0.45 MiB
example_01 AC 1 ms 0.45 MiB
max_00 AC 8 ms 0.45 MiB
max_01 AC 8 ms 0.45 MiB
max_02 AC 8 ms 0.46 MiB
max_1000000000_00 AC 8 ms 0.45 MiB
max_1000000000_01 AC 8 ms 0.45 MiB
max_1000000000_02 AC 8 ms 0.45 MiB
max_998244353_00 AC 17 ms 0.45 MiB
max_998244353_01 AC 17 ms 0.45 MiB
max_998244353_02 AC 17 ms 0.46 MiB
random_00 AC 6 ms 0.45 MiB
random_01 AC 2 ms 0.45 MiB
random_02 AC 1 ms 0.45 MiB
random_03 AC 2 ms 0.45 MiB
random_04 AC 5 ms 0.46 MiB
small_00 AC 1 ms 0.45 MiB

#include <bitset> #include <cmath> #include <cstdint> #include <cstdio> #include <queue> #include <functional> const uint32_t primemax = 31622; std::vector<uint32_t> primes; std::bitset<31622> primebit; void prec_primes() { primes.reserve(1.25506 * primemax / logl(primemax)); primebit.set(); primebit[0] = primebit[1] = false; for (uint32_t i = 2; i <= primemax; i++) { if (primebit[i]) { primes.push_back(i); for (uint32_t j = i * i; j <= primemax; j += i) primebit[j] = false; } } } uint32_t euler_totient(uint32_t n) { uint32_t ret = n, last; for (auto i : primes){ if (i * i > n) break; if (n % i == 0) { ret = ret / i * (i - 1); do { n /= i; } while (n % i == 0); } } if (n > 1) ret = ret / n * (n - 1); return ret; } uint32_t modex(uint32_t b, uint32_t e, uint32_t m) { uint32_t ret = 1; while (e) { if (e & 1) ret = (uint64_t) ret * b % m; b = (uint64_t) b * b % m; e >>= 1; } return ret; } uint32_t tetration_mod(uint32_t a, uint32_t b, uint32_t m) { // m in [1, 2 ** 31] if (a == 0) return (~ b & 1) % m; if (a == 1) return 1 % m; if (a == 2) { switch (b) { case 0: return 1 % m; case 1: return 2 % m; case 2: return 4 % m; case 3: return 16 % m; case 4: return 65536 % m; } std::function<uint32_t(uint32_t, uint32_t)> solve = [&solve](uint32_t b, uint32_t m) { if (m == 1) return 0u; if (b == 4) return 65536 % m; uint32_t nextm = euler_totient(m); return modex(2, solve(b - 1, nextm) + nextm, m); }; return solve(b, m); } if (a <= 9) { static const uint32_t b2_lookup[] = {1, 1, 4, 27, 256, 3125, 46656, 823543, 16777216, 387420489}; switch (b) { case 0: return 1 % m; case 1: return a % m; case 2: return b2_lookup[a] % m; } std::function<uint32_t(uint32_t, uint32_t)> solve = [&solve, &a](uint32_t b, uint32_t m) { if (m == 1) return 0u; if (b == 2) return b2_lookup[a]; uint32_t nextm = euler_totient(m); return modex(a, solve(b - 1, nextm) + nextm, m); }; return solve(b, m); } switch (b) { case 0: return 1 % m; case 1: return a % m; case 2: return modex(a, a, m); } std::function<uint32_t(uint32_t, uint32_t)> solve = [&solve, &a](uint32_t b, uint32_t m) { if (m == 1) return 0u; if (b == 2) return modex(a, a, m); uint32_t nextm = euler_totient(m); return modex(a, solve(b - 1, nextm) + nextm, m); }; return solve(b, m); } int main() { prec_primes(); uint32_t t; scanf("%u", &t); while (t--) { uint32_t a, b, m; scanf("%u%u%u", &a, &b, &m); printf("%u\n", tetration_mod(a, b, m)); } }