Submit Info #20818

Problem Lang User Status Time Memory
Tetration Mod cpp Nyaan AC 17 ms 0.77 MiB

ケース詳細
Name Status Time Memory
2_3_32_00 AC 2 ms 0.68 MiB
example_00 AC 1 ms 0.37 MiB
example_01 AC 1 ms 0.68 MiB
max_00 AC 9 ms 0.68 MiB
max_01 AC 8 ms 0.71 MiB
max_02 AC 9 ms 0.71 MiB
max_1000000000_00 AC 9 ms 0.77 MiB
max_1000000000_01 AC 7 ms 0.68 MiB
max_1000000000_02 AC 9 ms 0.68 MiB
max_998244353_00 AC 17 ms 0.68 MiB
max_998244353_01 AC 16 ms 0.68 MiB
max_998244353_02 AC 17 ms 0.68 MiB
random_00 AC 6 ms 0.75 MiB
random_01 AC 3 ms 0.68 MiB
random_02 AC 2 ms 0.75 MiB
random_03 AC 2 ms 0.67 MiB
random_04 AC 5 ms 0.71 MiB
small_00 AC 1 ms 0.75 MiB

#pragma region kyopro_template #define Nyaan_template #include <immintrin.h> #include <bits/stdc++.h> #define pb push_back #define eb emplace_back #define fi first #define se second #define each(x, v) for (auto &x : v) #define all(v) (v).begin(), (v).end() #define sz(v) ((int)(v).size()) #define mem(a, val) memset(a, val, sizeof(a)) #define ini(...) \ int __VA_ARGS__; \ in(__VA_ARGS__) #define inl(...) \ long long __VA_ARGS__; \ in(__VA_ARGS__) #define ins(...) \ string __VA_ARGS__; \ in(__VA_ARGS__) #define inc(...) \ char __VA_ARGS__; \ in(__VA_ARGS__) #define in2(s, t) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i]); \ } #define in3(s, t, u) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i], u[i]); \ } #define in4(s, t, u, v) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i], u[i], v[i]); \ } #define rep(i, N) for (long long i = 0; i < (long long)(N); i++) #define repr(i, N) for (long long i = (long long)(N)-1; i >= 0; i--) #define rep1(i, N) for (long long i = 1; i <= (long long)(N); i++) #define repr1(i, N) for (long long i = (N); (long long)(i) > 0; i--) #define reg(i, a, b) for (long long i = (a); i < (b); i++) #define die(...) \ do { \ out(__VA_ARGS__); \ return; \ } while (0) using namespace std; using ll = long long; template <class T> using V = vector<T>; using vi = vector<int>; using vl = vector<long long>; using vvi = vector<vector<int>>; using vd = V<double>; using vs = V<string>; using vvl = vector<vector<long long>>; using P = pair<long long, long long>; using vp = vector<P>; using pii = pair<int, int>; using vpi = vector<pair<int, int>>; constexpr int inf = 1001001001; constexpr long long infLL = (1LL << 61) - 1; template <typename T, typename U> inline bool amin(T &x, U y) { return (y < x) ? (x = y, true) : false; } template <typename T, typename U> inline bool amax(T &x, U y) { return (x < y) ? (x = y, true) : false; } template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) { os << p.first << " " << p.second; return os; } template <typename T, typename U> istream &operator>>(istream &is, pair<T, U> &p) { is >> p.first >> p.second; return is; } template <typename T> ostream &operator<<(ostream &os, const vector<T> &v) { int s = (int)v.size(); for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i]; return os; } template <typename T> istream &operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; } void in() {} template <typename T, class... U> void in(T &t, U &... u) { cin >> t; in(u...); } void out() { cout << "\n"; } template <typename T, class... U> void out(const T &t, const U &... u) { cout << t; if (sizeof...(u)) cout << " "; out(u...); } #ifdef NyaanDebug #define trc(...) \ do { \ cerr << #__VA_ARGS__ << " = "; \ dbg_out(__VA_ARGS__); \ } while (0) #define trca(v, N) \ do { \ cerr << #v << " = "; \ array_out(v, N); \ } while (0) #define trcc(v) \ do { \ cerr << #v << " = {"; \ each(x, v) { cerr << " " << x << ","; } \ cerr << "}" << endl; \ } while (0) template <typename T> void _cout(const T &c) { cerr << c; } void _cout(const int &c) { if (c == 1001001001) cerr << "inf"; else if (c == -1001001001) cerr << "-inf"; else cerr << c; } void _cout(const unsigned int &c) { if (c == 1001001001) cerr << "inf"; else cerr << c; } void _cout(const long long &c) { if (c == 1001001001 || c == (1LL << 61) - 1) cerr << "inf"; else if (c == -1001001001 || c == -((1LL << 61) - 1)) cerr << "-inf"; else cerr << c; } void _cout(const unsigned long long &c) { if (c == 1001001001 || c == (1LL << 61) - 1) cerr << "inf"; else cerr << c; } template <typename T, typename U> void _cout(const pair<T, U> &p) { cerr << "{ "; _cout(p.fi); cerr << ", "; _cout(p.se); cerr << " } "; } template <typename T> void _cout(const vector<T> &v) { int s = v.size(); cerr << "{ "; for (int i = 0; i < s; i++) { cerr << (i ? ", " : ""); _cout(v[i]); } cerr << " } "; } template <typename T> void _cout(const vector<vector<T>> &v) { cerr << "[ "; for (const auto &x : v) { cerr << endl; _cout(x); cerr << ", "; } cerr << endl << " ] "; } void dbg_out() { cerr << endl; } template <typename T, class... U> void dbg_out(const T &t, const U &... u) { _cout(t); if (sizeof...(u)) cerr << ", "; dbg_out(u...); } template <typename T> void array_out(const T &v, int s) { cerr << "{ "; for (int i = 0; i < s; i++) { cerr << (i ? ", " : ""); _cout(v[i]); } cerr << " } " << endl; } template <typename T> void array_out(const T &v, int H, int W) { cerr << "[ "; for (int i = 0; i < H; i++) { cerr << (i ? ", " : ""); array_out(v[i], W); } cerr << " ] " << endl; } #else #define trc(...) #define trca(...) #define trcc(...) #endif inline int popcnt(unsigned long long a) { return __builtin_popcountll(a); } inline int lsb(unsigned long long a) { return __builtin_ctzll(a); } inline int msb(unsigned long long a) { return 63 - __builtin_clzll(a); } template <typename T> inline int getbit(T a, int i) { return (a >> i) & 1; } template <typename T> inline void setbit(T &a, int i) { a |= (1LL << i); } template <typename T> inline void delbit(T &a, int i) { a &= ~(1LL << i); } template <typename T> int lb(const vector<T> &v, const T &a) { return lower_bound(begin(v), end(v), a) - begin(v); } template <typename T> int ub(const vector<T> &v, const T &a) { return upper_bound(begin(v), end(v), a) - begin(v); } template <typename T> int btw(T a, T x, T b) { return a <= x && x < b; } template <typename T, typename U> T ceil(T a, U b) { return (a + b - 1) / b; } constexpr long long TEN(int n) { long long ret = 1, x = 10; while (n) { if (n & 1) ret *= x; x *= x; n >>= 1; } return ret; } template <typename T> vector<T> mkrui(const vector<T> &v) { vector<T> ret(v.size() + 1); for (int i = 0; i < int(v.size()); i++) ret[i + 1] = ret[i] + v[i]; return ret; }; template <typename T> vector<T> mkuni(const vector<T> &v) { vector<T> ret(v); sort(ret.begin(), ret.end()); ret.erase(unique(ret.begin(), ret.end()), ret.end()); return ret; } template <typename F> vector<int> mkord(int N, F f) { vector<int> ord(N); iota(begin(ord), end(ord), 0); sort(begin(ord), end(ord), f); return ord; } template <typename T = int> vector<T> mkiota(int N) { vector<T> ret(N); iota(begin(ret), end(ret), 0); return ret; } template <typename T> vector<int> mkinv(vector<T> &v) { vector<int> inv(v.size()); for (int i = 0; i < (int)v.size(); i++) inv[v[i]] = i; return inv; } struct IoSetupNya { IoSetupNya() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(7); } } iosetupnya; void solve(); int main() { solve(); } #pragma endregion template <typename T = uint32_t, typename U = uint64_t, T MAX = 1000000000> T tetration(T a, T b, T m) { auto prime_table = [](T m) -> vector<int> { T thres = sqrt(m) + 1; vector<bool> flg(thres + 1); for (T i = 2; i * i <= thres; ++i) { if (!flg[i]) for (T j = i * i; j <= thres; j += i) flg[j] = 1; } vector<int> ret; for (T i = 2; i <= thres; i++) if (!flg[i]) ret.push_back(i); return ret; }; static const vector<int> ps = prime_table(MAX); auto totient = [&](T n) -> T { T ret = n; for (auto& p : ps) { if (p * p > n) break; if (n % p == 0) { ret = ret / p * (p - 1); while (n % p == 0) n /= p; } } if (n != 1) ret = ret / n * (n - 1); return ret; }; auto mpow = [](U a, U p, T m) -> pair<T, int> { U ret = 1 % m; int flg = true; for (; p; p >>= 1) { if (p & 1) if ((ret *= a) >= m) flg = 0, ret %= m; if (p == 1) break; if ((a *= a) >= m) flg = 0, a %= m; } return {ret, flg}; }; auto calc = [&](auto rec, T a, U b, T m) -> pair<T, int> { if (a == 0) return {!(b & 1), true}; if (a == 1) return {1, true}; if (m == 1) return {0, false}; if (b == 0) return {1, true}; if (b == 1) return {a % m, a < m}; T phi_m = totient(m), pre, ret; int flg1, flg2; tie(pre, flg1) = rec(rec, a, b - 1, phi_m); tie(ret, flg2) = mpow(a % m, U(pre) + (flg1 ? 0 : phi_m), m); return {ret, flg1 && flg2}; }; return calc(calc, a, b, m).first % m; } using namespace std; namespace fastio { static constexpr int SZ = 1 << 17; char ibuf[SZ], obuf[SZ]; int pil = 0, pir = 0, por = 0; struct Pre { char num[40000]; constexpr Pre() : num() { for (int i = 0; i < 10000; i++) { int n = i; for (int j = 3; j >= 0; j--) { num[i * 4 + j] = n % 10 + '0'; n /= 10; } } } } constexpr pre; inline void load() { memcpy(ibuf, ibuf + pil, pir - pil); pir = pir - pil + fread(ibuf + pir - pil, 1, SZ - pir + pil, stdin); pil = 0; } inline void flush() { fwrite(obuf, 1, por, stdout); por = 0; } inline void rd(char& c) { c = ibuf[pil++]; } template <typename T> inline void rd(T& x) { if (pil + 32 > pir) load(); char c; do c = ibuf[pil++]; while (c < '-'); bool minus = 0; if (c == '-') { minus = 1; c = ibuf[pil++]; } x = 0; while (c >= '0') { x = x * 10 + (c & 15); c = ibuf[pil++]; } if (minus) x = -x; } inline void rd() {} template <typename Head, typename... Tail> inline void rd(Head& head, Tail&... tail) { rd(head); rd(tail...); } inline void wt(char c) { obuf[por++] = c; } template <typename T> inline void wt(T x) { if (por > SZ - 32) flush(); if (!x) { obuf[por++] = '0'; return; } if (x < 0) { obuf[por++] = '-'; x = -x; } int i = 12; char buf[16]; while (x >= 10000) { memcpy(buf + i, pre.num + (x % 10000) * 4, 4); x /= 10000; i -= 4; } int d = x < 100 ? (x < 10 ? 1 : 2) : (x < 1000 ? 3 : 4); memcpy(obuf + por, pre.num + x * 4 + 4 - d, d); por += d; memcpy(obuf + por, buf + i + 4, 12 - i); por += 12 - i; } inline void wt() {} template <typename Head, typename... Tail> inline void wt(Head head, Tail... tail) { wt(head); wt(tail...); } template<typename T> inline void wtn(T x){ wt(x, '\n'); } struct Dummy { Dummy() { atexit(flush); } } dummy; } // namespace fastio using fastio::rd; using fastio::wt; using fastio::wtn; void solve() { int T; rd(T); rep(i, T) { uint32_t a, b, m; rd(a, b, m); wtn(tetration(a, b, m)); } }