Submit Info #56862

Problem Lang User Status Time Memory
Tetration Mod cpp tokusakurai AC 79 ms 0.72 MiB

ケース詳細
Name Status Time Memory
2_3_32_00 AC 1 ms 0.71 MiB
example_00 AC 1 ms 0.61 MiB
example_01 AC 1 ms 0.71 MiB
max_00 AC 17 ms 0.71 MiB
max_01 AC 18 ms 0.71 MiB
max_02 AC 17 ms 0.71 MiB
max_1000000000_00 AC 9 ms 0.62 MiB
max_1000000000_01 AC 9 ms 0.70 MiB
max_1000000000_02 AC 9 ms 0.71 MiB
max_998244353_00 AC 79 ms 0.71 MiB
max_998244353_01 AC 79 ms 0.71 MiB
max_998244353_02 AC 79 ms 0.72 MiB
random_00 AC 12 ms 0.71 MiB
random_01 AC 4 ms 0.71 MiB
random_02 AC 2 ms 0.71 MiB
random_03 AC 4 ms 0.61 MiB
random_04 AC 10 ms 0.71 MiB
small_00 AC 1 ms 0.71 MiB

#include <bits/stdc++.h> using namespace std; struct io_setup{ io_setup(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout << fixed << setprecision(15); } } io_setup; struct Random_Number_Generator{ mt19937_64 mt; Random_Number_Generator() : mt(chrono::steady_clock::now().time_since_epoch().count()) {} int64_t operator () (int64_t l, int64_t r){ //[l,r)で乱数発生 uniform_int_distribution<int64_t> dist(l, r-1); return dist(mt); } int64_t operator () (int64_t r){ //[0,r)で乱数発生 return (*this)(0, r); } }; long long modpow(long long x, long long n, const int &m){ long long ret = 1; for(; n > 0; n >>= 1, x *= x, x %= m){ if(n&1) ret *= x, ret %= m; } return ret; } template<typename T> T Euler_Totient(T m){ //オイラーのφ関数(xとmが互いに素ならば、x^φ(m)≡1(mod m)) T ret = m; for(T i = 2; i*i <= m; i++){ if(m%i == 0) ret /= i, ret *= i-1; while(m%i == 0) m /= i; } if(m > 1) ret /= m, ret *= m-1; return ret; } int modlog(const int &x, long long y, const int &m){ //x^k=y(mod m)となる最小の非負整数k(xとmは互いに素) unordered_map<int, int> mp; int n = 0; long long now = 1; for(; n*n < m; n++){ if(!mp.count(now)) mp[now] = n; now *= x, now %= m; } now = modpow(now, Euler_Totient(m)-1, m); for(int i = 0; i < n; i++){ if(mp.count(y)) return n*i+mp[y]; y *= now, y %= m; } return -1; } template<typename T> T order(T x, const T &m){ //x^k=1(mod m)となる最小の正整数k(xとmは互いに素) T n = Euler_Totient(m); vector<T> ds; for(T i = 1; i*i <= n; i++){ if(n%i == 0) ds.push_back(i), ds.push_back(n/i); } sort(begin(ds), end(ds)); for(auto &e: ds){ if(modpow(x, e, m) == 1) return e; } return -1; } template<typename T> T primitive_root(const T &m){ //素数mの原始根 vector<T> ds; for(T i = 1; i*i <= m-1; i++){ if((m-1)%i == 0) ds.push_back(i), ds.push_back((m-1)/i); } sort(begin(ds), end(ds)); Random_Number_Generator rng; while(true){ T r = rng(1, m); for(auto &e: ds){ if(e == m-1) return r; if(modpow(r, e, m) == 1) break; } } } long long modpow(long long x, long long n, const int &m, int &flag){ //答えがm以上になるならflagを立てる long long ret = 1; for(; n > 0; n >>= 1, x *= x, x %= m){ if(n&1){ ret *= x; if(ret >= m) flag = 1, ret %= m; } } return ret; } long long modtetration(const long long &x, const long long &n, const int &m, int &flag){ //flagが立っていればa^bは周期に入っている if(m == 1) return flag = 1; if(x == 0) return (n&1? 0 : 1); if(x == 1 || n == 0) return 1; if(n == 1){ if(x >= m) flag = 1; return x%m+flag*m; } long long tmp = modtetration(x, n-1, Euler_Totient(m), flag); long long ret = modpow(x, tmp, m, flag); return ret+flag*m; } long long modtetration(const long long &x, const long long &n, const int &m){ int flag = 0; return modtetration(x, n, m, flag)%m; } int main(){ int T; cin >> T; while(T--){ long long x, n, m; cin >> x >> n >> m; cout << modtetration(x, n, m) << '\n'; } }