Submit Info #11470

Problem Lang User Status Time Memory
Tetration Mod cpp YouKn0wWho AC 23 ms 0.80 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.67 MiB
example_01 AC 2 ms 0.70 MiB
max_00 AC 23 ms 0.80 MiB
max_01 AC 20 ms 0.80 MiB
max_02 AC 17 ms 0.74 MiB
max_1000000000_00 AC 10 ms 0.68 MiB
max_1000000000_01 AC 13 ms 0.68 MiB
max_1000000000_02 AC 11 ms 0.68 MiB
max_998244353_00 AC 16 ms 0.71 MiB
max_998244353_01 AC 14 ms 0.72 MiB
max_998244353_02 AC 15 ms 0.71 MiB
random_00 AC 14 ms 0.67 MiB
random_01 AC 6 ms 0.68 MiB
random_02 AC 4 ms 0.67 MiB
random_03 AC 0 ms 0.72 MiB
random_04 AC 11 ms 0.72 MiB
small_00 AC 1 ms 0.71 MiB

#include<bits/stdc++.h> using namespace std; const int N = 3e5 + 9; #define MOD(a, mod) (a < mod ? a : a % mod + mod) int power(long long n, long long k, const int mod) { long long ans = MOD(1, mod); while (k) { if (k & 1) ans = MOD(ans * n, mod); n = MOD(n * n, mod); k >>= 1; } return ans; } unordered_map<int, int> mp; int totient(int n) { if (mp.find(n) != mp.end()) return mp[n]; int ans = n; for (int i = 2; i * i <= n; i++) { if (n % i == 0) { while (n % i == 0) n /= i; ans = ans / i * (i - 1); } } if (n > 1) ans = ans / n * (n - 1); return mp[n] = ans; } int yo(int a, int b, int mod) { if (a == 0) return MOD((b + 1) % 2, mod); if (b == 0) return MOD(1, mod); if (mod == 1) return MOD(1, mod); return power(a, yo(a, b - 1, totient(mod)), mod); } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while (t--) { int a, b, m; cin >> a >> b >> m; cout << yo(a, b, m) % m << '\n'; } return 0; }