Submit Info #2034

Problem Lang User Status Time Memory
Tetration Mod cpp kyoprofriends AC 488 ms 0.72 MiB

ケース詳細
Name Status Time Memory
example_00 AC 0 ms 0.67 MiB
example_01 AC 1 ms 0.72 MiB
max_00 AC 82 ms 0.67 MiB
max_01 AC 79 ms 0.67 MiB
max_02 AC 78 ms 0.61 MiB
max_1000000000_00 AC 19 ms 0.67 MiB
max_1000000000_01 AC 22 ms 0.61 MiB
max_1000000000_02 AC 23 ms 0.68 MiB
max_998244353_00 AC 488 ms 0.72 MiB
max_998244353_01 AC 487 ms 0.67 MiB
max_998244353_02 AC 487 ms 0.66 MiB
random_00 AC 54 ms 0.67 MiB
random_01 AC 16 ms 0.71 MiB
random_02 AC 12 ms 0.68 MiB
random_03 AC 16 ms 0.72 MiB
random_04 AC 46 ms 0.71 MiB
small_00 AC 2 ms 0.69 MiB

#include<stdio.h> #define ll long long ll phi(ll n) {ll s=n;for(ll i=2;i*i<=n;i++)if(n%i==0)for(s-=s/i;n%i<1;n/=i);return n==1?s:s-s/n;} ll pom(ll a,ll n,int m){ll x=1;for(a%=m;n;n/=2)n&1?x=x*a%m:0,a=a*a%m;return x;} int modtetra(int a,int n,int m){ if(m==1)return 0; if(n==0)return 1; if(a==0)return !(n%2); if(n==1)return a%m; if(n==2)return pom(a%m,a,m); if(n==3&&a==2)return 16%m; return pom(a%m,modtetra(a,n-1,phi(m))+phi(m),m); } int main(){ int t; scanf("%d",&t); while(t--){ int a,n,m; scanf("%d%d%d",&a,&n,&m); printf("%d\n",modtetra(a,n,m)); } }