結果
問題 | No.181 A↑↑N mod M |
ユーザー | r1933 |
提出日時 | 2020-09-24 18:31:49 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 5,088 bytes |
コンパイル時間 | 2,046 ms |
コンパイル使用メモリ | 202,772 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-28 05:15:23 |
合計ジャッジ時間 | 3,371 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 1 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 2 ms
5,376 KB |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | AC | 2 ms
5,376 KB |
testcase_20 | AC | 2 ms
5,376 KB |
testcase_21 | AC | 2 ms
5,376 KB |
testcase_22 | AC | 2 ms
5,376 KB |
testcase_23 | AC | 2 ms
5,376 KB |
testcase_24 | AC | 2 ms
5,376 KB |
testcase_25 | AC | 2 ms
5,376 KB |
testcase_26 | AC | 2 ms
5,376 KB |
testcase_27 | AC | 2 ms
5,376 KB |
testcase_28 | AC | 2 ms
5,376 KB |
testcase_29 | AC | 2 ms
5,376 KB |
testcase_30 | AC | 2 ms
5,376 KB |
testcase_31 | AC | 2 ms
5,376 KB |
testcase_32 | AC | 2 ms
5,376 KB |
testcase_33 | AC | 2 ms
5,376 KB |
testcase_34 | AC | 2 ms
5,376 KB |
testcase_35 | AC | 2 ms
5,376 KB |
testcase_36 | AC | 2 ms
5,376 KB |
testcase_37 | AC | 2 ms
5,376 KB |
testcase_38 | AC | 2 ms
5,376 KB |
testcase_39 | AC | 2 ms
5,376 KB |
testcase_40 | AC | 2 ms
5,376 KB |
testcase_41 | AC | 2 ms
5,376 KB |
testcase_42 | AC | 2 ms
5,376 KB |
ソースコード
#include "bits/stdc++.h" // Begin Header {{{ #pragma region using namespace std; using imax = intmax_t; using usize = size_t; using ld = long double; #ifndef DEBUG #define dump(...) #endif #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) #define rep(i, b, e) for (intmax_t i = (b), i##_limit = (e); i < i##_limit; ++i) #define repc(i, b, e) for (intmax_t i = (b), i##_limit = (e); i <= i##_limit; ++i) #define repr(i, b, e) for (intmax_t i = (b), i##_limit = (e); i >= i##_limit; --i) #define var(Type, ...) Type __VA_ARGS__; input(__VA_ARGS__) #define let const auto constexpr size_t operator""_zu(unsigned long long value) { return value; }; constexpr intmax_t operator""_jd(unsigned long long value) { return value; }; constexpr uintmax_t operator""_ju(unsigned long long value) { return value; }; constexpr int INF = 0x3f3f3f3f; constexpr intmax_t LINF = 0x3f3f3f3f3f3f3f3f_jd; template <class T, class Compare = less<>> using MaxHeap = priority_queue<T, vector<T>, Compare>; template <class T, class Compare = greater<>> using MinHeap = priority_queue<T, vector<T>, Compare>; inline void input() {} template <class Head, class... Tail> inline void input(Head&& head, Tail&&... tail) { cin >> head; input(forward<Tail>(tail)...); } template <class Container, class Value = typename Container::value_type, enable_if_t<!is_same<Container, string>::value, nullptr_t> = nullptr> inline istream& operator>>(istream &is, Container &vs) { for (auto &v: vs) is >> v; return is; } inline void output() { cout << "\n"; } template <class Head, class... Tail> inline void output(Head&& head, Tail&&... tail) { cout << head; if (sizeof...(tail)) cout << " "; output(forward<Tail>(tail)...); } template <class Container, class Value = typename Container::value_type, enable_if_t<!is_same<Container, string>::value, nullptr_t> = nullptr> inline ostream& operator<<(ostream &os, const Container &vs) { static constexpr const char *delim[] = {" ", ""}; for (auto it = begin(vs); it != end(vs); ++it) { os << delim[it == begin(vs)] << *it; } return os; } template <class Iterator> inline void join(const Iterator &Begin, const Iterator &End, const string &delim = "\n", const string &last = "\n") { for (auto it = Begin; it != End; ++it) { cout << ((it == Begin) ? "" : delim) << *it; } cout << last; } template <class T> inline vector<T> makeVector(const T &initValue, size_t sz) { return vector<T>(sz, initValue); } template <class T, class... Args> inline auto makeVector(const T &initValue, size_t sz, Args... args) { return vector<decltype(makeVector<T>(initValue, args...))>(sz, makeVector<T>(initValue, args...)); } template <class Func> class FixPoint : Func { public: explicit constexpr FixPoint(Func&& f) noexcept : Func(forward<Func>(f)) {} template <class... Args> constexpr decltype(auto) operator()(Args&&... args) const { return Func::operator()(*this, std::forward<Args>(args)...); } }; template <class Func> static inline constexpr decltype(auto) makeFixPoint(Func&& f) noexcept { return FixPoint<Func>{forward<Func>(f)}; } template <class Container> struct reverse_t { Container &c; reverse_t(Container &c) : c(c) {} auto begin() { return c.rbegin(); } auto end() { return c.rend(); } }; template <class Container> auto reversed(Container &c) { return reverse_t<Container>(c); } template <class T> inline bool chmax(T &a, const T &b) noexcept { return b > a && (a = b, true); } template <class T> inline bool chmin(T &a, const T &b) noexcept { return b < a && (a = b, true); } template <class T> inline T diff(const T &a, const T &b) noexcept { return a < b ? b - a : a - b; } void ioinit() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(10); cerr << fixed << setprecision(10); clog << fixed << setprecision(10); } #pragma endregion // }}} End Header intmax_t totient(intmax_t n) { intmax_t ret = n; for (intmax_t i = 2; i * i <= n; ++i) { if (n % i == 0) { ret -= ret / i; while (n % i == 0) { n /= i; } } } if (n > 1) { ret -= ret / n; } return ret; } intmax_t power(intmax_t b, intmax_t e, intmax_t m) { intmax_t ret = 1; for (intmax_t i = e; i > 0; i >>= 1) { if (i & 1) { ret = (ret * b) % m; } b = (b * b) % m; } return ret; } intmax_t tetration(intmax_t a, intmax_t b, intmax_t m) { if (m == 1) return 0; if (a == 0) return ~b & 1; if (b == 0) return 1; if (b == 1) return a % m; if (b == 2) return power(a % m, a, m); if (a == 2 && b == 3) return 16 % m; if (a == 3 && b == 3) return power(3, 27, m); if (a == 2 && b == 4) return (1_jd << 16) % m; return power(a, tetration(a, b - 1, totient(m)) + totient(m), m); } signed main() { ioinit(); var(imax, A, B, M); output(tetration(A, B, M)); return 0; }