Submit Info #5768

Problem Lang User Status Time Memory
Tetration Mod cpp chocorusk AC 264 ms 0.72 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.72 MiB
example_01 AC 2 ms 0.67 MiB
max_00 AC 48 ms 0.68 MiB
max_01 AC 47 ms 0.68 MiB
max_02 AC 48 ms 0.70 MiB
max_1000000000_00 AC 16 ms 0.67 MiB
max_1000000000_01 AC 11 ms 0.68 MiB
max_1000000000_02 AC 20 ms 0.67 MiB
max_998244353_00 AC 263 ms 0.68 MiB
max_998244353_01 AC 264 ms 0.70 MiB
max_998244353_02 AC 259 ms 0.68 MiB
random_00 AC 34 ms 0.72 MiB
random_01 AC 12 ms 0.69 MiB
random_02 AC 6 ms 0.68 MiB
random_03 AC 12 ms 0.69 MiB
random_04 AC 25 ms 0.69 MiB
small_00 AC 1 ms 0.67 MiB

#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair<int, int> P; ll powmod(ll a, ll k, ll mod){ ll ap=a, ans=1; while(k){ if(k&1){ ans*=ap; ans%=mod; } ap=ap*ap; ap%=mod; k>>=1; } return ans; } ll phi(ll m){ ll ret=m; for(ll i=2; i*i<=m; i++){ if(m%i==0){ m/=i; ret/=i; ret*=(i-1); while(m%i==0) m/=i; } } if(m>1){ ret/=m; ret*=(m-1); } return ret; } ll tetration(ll a, ll b, ll m){ if(m==1) return 0; if(b==0) return 1; if(a==0){ if(b&1) return 0; else return 1; }else if(a==1) return 1; else if(b==1) return a%m; else if(b==2) return powmod(a%m, a, m); else if(a==2 && b==3) return 16%m; else if(a==2 && b==4) return (1<<16)%m; else if(a==3 && b==3) return powmod(3%m, 27, m); ll p=phi(m); return powmod(a%m, 30*p+tetration(a, b-1, p), m); } int main() { int t; scanf("%d", &t); while(t--){ ll a, b, m; scanf("%lld %lld %lld", &a, &b, &m); printf("%lld\n", tetration(a, b, m)); } return 0; }