Submit Info #58310

Problem Lang User Status Time Memory
Tetration Mod cpp14 shanem_1401 AC 152 ms 0.43 MiB

ケース詳細
Name Status Time Memory
2_3_32_00 AC 0 ms 0.41 MiB
example_00 AC 0 ms 0.41 MiB
example_01 AC 0 ms 0.42 MiB
max_00 AC 28 ms 0.36 MiB
max_01 AC 28 ms 0.41 MiB
max_02 AC 31 ms 0.41 MiB
max_1000000000_00 AC 12 ms 0.42 MiB
max_1000000000_01 AC 11 ms 0.42 MiB
max_1000000000_02 AC 12 ms 0.41 MiB
max_998244353_00 AC 152 ms 0.41 MiB
max_998244353_01 AC 151 ms 0.38 MiB
max_998244353_02 AC 149 ms 0.41 MiB
random_00 AC 19 ms 0.41 MiB
random_01 AC 6 ms 0.43 MiB
random_02 AC 3 ms 0.42 MiB
random_03 AC 5 ms 0.41 MiB
random_04 AC 15 ms 0.41 MiB
small_00 AC 1 ms 0.42 MiB

#include <stdio.h> typedef long long ll; int tc, n, k, m; int cnt_phi(int n) { int res=n; for(int i=2; i*i<=n; i++) { if(n%i==0) { while(n%i==0) n/=i; res-=res/i; } } if(n>1) res-=res/n; return res; } int modexp(int b, int e, int m) { bool state=false; if(e>=cnt_phi(m)) state=true; int r=1; while(e) { if(e&1) { if((1ll*r*b)>(ll)m) state=true; r=(1ll*r*b)%m; } if(1ll*b*b>(ll)m) state=true; b=(1ll*b*b)%m; e>>=1; } if(state) return r+m; else return r; } int f(int a, int b, int modd) { if(a==0) return ~b&1; if(a==1 || modd==1) return 1; if(b==1) { if(a>=modd) return a%modd+modd; else return a; } int pangkat=f(a, b-1, cnt_phi(modd)); int res=modexp(a, pangkat, modd); return res; //printf("pangkat: %d, modd: %d\n", pangkat, modd); } int main() { scanf("%d",& tc); while(tc--) { scanf("%d %d %d",& n,& k,& m); if(k==0) { if(m==1) printf("0\n"); else printf("1\n"); } else printf("%d\n", f(n, k, m)%m); } }