Submit Info #53617

Problem Lang User Status Time Memory
Tetration Mod cpp kenpegrasio AC 137 ms 0.61 MiB

ケース詳細
Name Status Time Memory
2_3_32_00 AC 0 ms 0.61 MiB
example_00 AC 0 ms 0.61 MiB
example_01 AC 0 ms 0.61 MiB
max_00 AC 42 ms 0.61 MiB
max_01 AC 41 ms 0.61 MiB
max_02 AC 42 ms 0.61 MiB
max_1000000000_00 AC 17 ms 0.61 MiB
max_1000000000_01 AC 17 ms 0.61 MiB
max_1000000000_02 AC 17 ms 0.61 MiB
max_998244353_00 AC 137 ms 0.61 MiB
max_998244353_01 AC 137 ms 0.61 MiB
max_998244353_02 AC 135 ms 0.61 MiB
random_00 AC 29 ms 0.60 MiB
random_01 AC 9 ms 0.61 MiB
random_02 AC 4 ms 0.61 MiB
random_03 AC 8 ms 0.61 MiB
random_04 AC 21 ms 0.61 MiB
small_00 AC 0 ms 0.61 MiB

#include<stdio.h> #include<math.h> typedef long long LL; using namespace std; bool isPrime(LL n) { LL b=sqrt(n)+1; if(n==1) return false; if(n%2==0 && n!=2) return false; for(LL a=3;a<=b;a+=2) { if(n%a==0) return false; } return true; } LL euler(LL n) { if(isPrime(n)) return n-1; else { LL bantuan = n; for(LL a=2;a*a<=n;a++) { if(n%a==0) bantuan = bantuan *(a-1)/a; while(n%a==0) n=n/a; } if(n>1) bantuan = bantuan/n*(n-1); return bantuan; } } LL fast_exponent(LL a, LL b, LL m) { if(b==0) return 1; else if(b==1) return a%m; else { LL hasil = fast_exponent(a, b/2,m); hasil = (hasil%m * hasil%m); if(b&1) hasil = (hasil%m*a%m); return hasil % m; } } LL tetration_mod(LL a,LL b,LL m) { if(m==1) return 0; if(b==1) return a%m; if(b==0) return 1; if(a==0) { if(b%2==0) return 1; else return 0; } if(a==1) return 1; if(b==2) return fast_exponent(a,a,m); if(a==2) { if(b==3) return 16%m; if(b==4) return 65536%m; } LL rec=euler(m); return fast_exponent(a, tetration_mod(a, b-1, rec)+rec, m); } int main() { int testcase; scanf("%d",&testcase); for(int i=1;i<=testcase;i++) { LL a,b,m; scanf("%lld%lld%lld",&a,&b,&m); printf("%lld\n",tetration_mod(a,b,m)); } }