Submit Info #2022

Problem Lang User Status Time Memory
Tetration Mod cpp (anonymous) AC 227 ms 0.72 MiB

ケース詳細
Name Status Time Memory
example_00 AC 4 ms 0.71 MiB
example_01 AC 2 ms 0.67 MiB
max_00 AC 38 ms 0.72 MiB
max_01 AC 36 ms 0.68 MiB
max_02 AC 34 ms 0.72 MiB
max_1000000000_00 AC 10 ms 0.72 MiB
max_1000000000_01 AC 8 ms 0.68 MiB
max_1000000000_02 AC 9 ms 0.67 MiB
max_998244353_00 AC 227 ms 0.68 MiB
max_998244353_01 AC 227 ms 0.68 MiB
max_998244353_02 AC 226 ms 0.71 MiB
random_00 AC 21 ms 0.71 MiB
random_01 AC 14 ms 0.68 MiB
random_02 AC 6 ms 0.67 MiB
random_03 AC 9 ms 0.68 MiB
random_04 AC 21 ms 0.72 MiB
small_00 AC 6 ms 0.68 MiB

// written by MMNMM (@259_Momone) #include<iostream> #include<algorithm> unsigned long carmichael_lambda(unsigned long n){ if(!(n & 7))n >>= 1; unsigned long r{1}; for(unsigned long i{2}; i * i <= n; ++i)if(n % i == 0){ unsigned long k{i - 1}; while((n /= i) % i == 0)k *= i; r *= k / std::__gcd(r, k); } if(n != 1)r *= (n - 1) / std::__gcd(r, n - 1); return r; } std::pair<bool, unsigned long> tetration_mod(unsigned long a, unsigned long b, unsigned long m, unsigned long lim = 64){ if(b == 0){ bool f{1 >= lim}; return {f, f ? 1 % m + f * (m * ((lim + m - 1) / m)) : 1}; } if(m == 1){ bool f{a >= lim}; return {f, f ? (m * ((lim + m - 1) / m)) : a}; } if(a == 0){ bool f{(~b & 1) >= lim}; return {f, (~b & 1) % m + f * (m * ((lim + m - 1) / m))}; } struct Int{ bool first; unsigned long second; unsigned long mod, maxord; Int(unsigned long _mod) : mod(_mod), maxord(64), first(true), second(1) {} Int(unsigned long _second, unsigned long _mod, unsigned long _maxord = 64) : mod(_mod), maxord(_maxord), second(_second){first = _second <= maxord;} Int(const bool _first, const unsigned long _second, unsigned long _mod, unsigned long _maxord = 64) : mod(_mod), maxord(_maxord), first(_first), second(_second){} Int(const std::pair<bool, unsigned long>& _f, unsigned long _mod, unsigned long _maxord = 64) : mod(_mod), maxord(_maxord), first(_f.first), second(_f.second){} Int& operator=(const Int& src) = default; Int operator*(const Int& t2){ Int ret(mod); auto t1 = *this; if(t1.first && t2.first){ ret.second = t1.second * t2.second; if(ret.second > maxord){ ret.first = false; ret.second %= mod; ret.second += mod * ((maxord + mod - 1) / mod); } }else{ ret.first = false; ret.second = (t1.second % mod) * (t2.second % mod) % mod + mod * ((maxord + mod - 1) / mod); } return ret; } Int modpow(unsigned long n){ Int A{*this}; Int ret(mod); while(n){ if(n & 1)ret = ret * A; A = A * A; n /= 2; } return ret; } }; Int f(a, m, lim), t(tetration_mod(a, b - 1, carmichael_lambda(m), lim), m, lim); auto ret = f.modpow(t.second); return {ret.first, ret.second}; } int main(){ using namespace std; unsigned long T; cin >> T; for(unsigned long iter{0}; iter < T; ++iter){ unsigned long A, B, M; cin >> A >> B >> M; cout << tetration_mod(A, B, M).second % M << endl; } return 0; }