Submit Info #15721

Problem Lang User Status Time Memory
Tetration Mod cpp14 Tweetuzki AC 91 ms 0.72 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.68 MiB
example_01 AC 2 ms 0.67 MiB
max_00 AC 23 ms 0.71 MiB
max_01 AC 25 ms 0.69 MiB
max_02 AC 23 ms 0.42 MiB
max_1000000000_00 AC 14 ms 0.67 MiB
max_1000000000_01 AC 14 ms 0.67 MiB
max_1000000000_02 AC 14 ms 0.72 MiB
max_998244353_00 AC 88 ms 0.72 MiB
max_998244353_01 AC 91 ms 0.72 MiB
max_998244353_02 AC 87 ms 0.67 MiB
random_00 AC 16 ms 0.67 MiB
random_01 AC 6 ms 0.72 MiB
random_02 AC 4 ms 0.67 MiB
random_03 AC 6 ms 0.68 MiB
random_04 AC 15 ms 0.68 MiB
small_00 AC 2 ms 0.68 MiB

#include <algorithm> #include <cstdio> #include <cstring> #include <vector> inline std::vector<int> factorize(int n) { std::vector<int> res; for (int i = 2; i * i <= n; ++i) { if (n % i == 0) { res.push_back(i); while (n % i == 0) n /= i; } } if (n != 1) res.push_back(n); return res; } inline int fastPow(int low, int high, int mod) { int res = 1; while (high) { if (high & 1) res = 1LL * res * low % mod; high >>= 1; low = 1LL * low * low % mod; } return res; } inline int getPhi(int n) { std::vector<int> prs = factorize(n); int phi = n; for (int i = 0; i < (int) prs.size(); ++i) phi = phi / prs[i] * (prs[i] - 1); return phi; } int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } inline bool overflow_fastpow(int a, int b, int mod) { if (mod == 1) { if (a == 0 && b != 0) return false; else return true; } if (a <= 1) return false; for (int i = 1, x = 1; i <= b; ++i) { if (1LL * x * a >= mod) return true; x *= a; } return false; } inline bool overflow_tetration(int a, int b, int mod) { if (b == 0) return false; if (b == 1) return a >= mod; int res = a; for (int i = 2; i <= b; ++i) { if (overflow_fastpow(a, res, mod) == true) return true; a = fastPow(a, res, mod); } return false; } int calc(int a, int b, int mod) { if (mod == 1) return 0; if (b == 0) return 1; if (b == 1) return a % mod; int phi = getPhi(mod); if (gcd(a, mod) == 1) return fastPow(a, calc(a, b - 1, phi), mod); else { if (overflow_tetration(a, b - 1, phi) == false) return fastPow(a, calc(a, b - 1, phi), mod); else return fastPow(a, calc(a, b - 1, phi) + phi, mod); } } int main() { int t; scanf("%d", &t); while (t--) { int a, b, m; scanf("%d %d %d", &a, &b, &m); if (a == 0) { if (m == 1) puts("0"); else if (b % 2 == 1) puts("0"); else puts("1"); } else printf("%d\n", calc(a, b, m)); } return 0; }