Submit Info #4054

Problem Lang User Status Time Memory
Tetration Mod cpp TKO919 AC 84 ms 0.72 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.71 MiB
example_01 AC 3 ms 0.68 MiB
max_00 AC 21 ms 0.71 MiB
max_01 AC 18 ms 0.67 MiB
max_02 AC 18 ms 0.68 MiB
max_1000000000_00 AC 12 ms 0.70 MiB
max_1000000000_01 AC 11 ms 0.68 MiB
max_1000000000_02 AC 10 ms 0.67 MiB
max_998244353_00 AC 84 ms 0.69 MiB
max_998244353_01 AC 84 ms 0.68 MiB
max_998244353_02 AC 84 ms 0.72 MiB
random_00 AC 14 ms 0.69 MiB
random_01 AC 4 ms 0.67 MiB
random_02 AC 5 ms 0.70 MiB
random_03 AC 8 ms 0.69 MiB
random_04 AC 11 ms 0.69 MiB
small_00 AC 2 ms 0.71 MiB

#define _USE_MATH_DEFINES #include <bits/stdc++.h> using namespace std; //template #define rep(i,a,b) for(int i=(a);i<(b);i++) #define rrep(i,a,b) for(int i=(a);i>(b);i--) #define ALL(v) (v).begin(),(v).end() typedef long long int ll; const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; const double eps=1e-12; void tostr(ll x,string& res){while(x)res+=('0'+(x%10)),x/=10; reverse(ALL(res)); return;} template<class T> inline bool chmax(T& a,T b){ if(a<b){a=b;return 1;}return 0; } template<class T> inline bool chmin(T& a,T b){ if(a>b){a=b;return 1;}return 0; } //template end int phi(int n){ int res=n; for(int i=2;i*i<=n;i++)if(n%i==0){ res=res/i*(i-1); while(n%i==0)n/=i; } if(n!=1)res=res/n*(n-1); return res; } int mpow(int a,int k,int m){ int res=1; while(k){ if(k&1)res=1LL*res*a%m; a=1LL*a*a%m; k>>=1; } return res; } int tetra(int a,int b,int 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 mpow(a%m,a,m); int p=phi(m); return mpow(a%m,tetra(a,b-1,p)+p,m); } int main(){ int t; scanf("%d",&t); rep(rot,0,t){ int a,b,m; scanf("%d%d%d",&a,&b,&m); printf("%d\n",tetra(a,b,m)%m); } return 0; }