Submit Info #34591

Problem Lang User Status Time Memory
Tetration Mod cpp pyranine AC 45 ms 0.74 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.48 MiB
example_01 AC 1 ms 0.67 MiB
max_00 AC 41 ms 0.74 MiB
max_01 AC 43 ms 0.67 MiB
max_02 AC 45 ms 0.67 MiB
max_1000000000_00 AC 13 ms 0.67 MiB
max_1000000000_01 AC 10 ms 0.62 MiB
max_1000000000_02 AC 13 ms 0.64 MiB
max_998244353_00 AC 15 ms 0.61 MiB
max_998244353_01 AC 17 ms 0.68 MiB
max_998244353_02 AC 19 ms 0.59 MiB
random_00 AC 31 ms 0.67 MiB
random_01 AC 10 ms 0.71 MiB
random_02 AC 7 ms 0.67 MiB
random_03 AC 10 ms 0.72 MiB
random_04 AC 24 ms 0.65 MiB
small_00 AC 1 ms 0.62 MiB

#include <bits/stdc++.h> using namespace std; using Int8 = int8_t; using Int16 = int16_t; using Int32 = int32_t; using Int64 = int64_t; using Int128 = __int128_t; using Word8 = uint8_t; using Word16 = uint16_t; using Word32 = uint32_t; using Word64 = uint64_t; using Word128 = __uint128_t; using Int = int_fast64_t; using Word = uint_fast64_t; using F32 = float; using F64 = double; using F80 = long double; using VS = vector<string>; using VVS = vector<vector<string>>; using VB = vector<bool>; using VVB = vector<vector<bool>>; using VI = vector<Int>; using VW = vector<Word>; using VVI = vector<vector<Int>>; using VVW = vector<vector<Word>>; using PII = pair<Int,Int>; using PWW = pair<Word,Word>; using VPII = vector<pair<Int,Int>>; using VPWW = vector<pair<Word,Word>>; #define LOOP(n) for(Int _ipiewnsjiw=0; _ipiewnsjiw<(n); _ipiewnsjiw++) #define REP(i,n) for(Int i=0, i##_len=(n); i<i##_len; ++i) #define RANGE(i,a,b) for(Int i=(a), i##_len(b); i<=i##_len; ++i) #define SZ(obj) ((Int)(obj).size()) #define UNIQUE(obj) (obj).erase(unique((obj).begin(),(obj).end()),(obj).end()) #define ALL(obj) (obj).begin(),(obj).end() #define RALL(obj) (obj).rbegin(),(obj).rend() using int32 = int_fast32_t; const int32 N = 300009; #define MOD(a,mod) ((a)<(mod)?(a):(a)%(mod)+(mod)) int32 power(Int n, Int k, const int32 mod) { Int 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<int32,int32> mp; int32 totient(int32 n) { if (mp.find(n) != mp.end()) { return mp[n]; } int32 ans = n; for (int32 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; } /* a ↑↑ b (mod m) */ int32 tetration(int32 a, int32 b, int32 m) { if (a == 0) return MOD((b + 1) % 2, m); if (b == 0) return MOD(1, m); if (m == 1) return MOD(1, m); return power(a, tetration(a, b - 1, totient(m)), m); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int Q; cin >> Q; while (Q--) { int a, b, m; cin >> a >> b >> m; cout << tetration(a, b, m) % m << '\n'; } return 0; }