Submit Info #47425

Problem Lang User Status Time Memory
Tetration Mod cpp NicholasPatrick AC 19 ms 0.83 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.81 MiB
example_01 AC 1 ms 0.80 MiB
max_00 AC 9 ms 0.78 MiB
max_01 AC 9 ms 0.71 MiB
max_02 AC 9 ms 0.80 MiB
max_1000000000_00 AC 8 ms 0.77 MiB
max_1000000000_01 AC 9 ms 0.80 MiB
max_1000000000_02 AC 10 ms 0.75 MiB
max_998244353_00 AC 18 ms 0.80 MiB
max_998244353_01 AC 19 ms 0.82 MiB
max_998244353_02 AC 19 ms 0.80 MiB
random_00 AC 7 ms 0.83 MiB
random_01 AC 4 ms 0.80 MiB
random_02 AC 2 ms 0.80 MiB
random_03 AC 2 ms 0.71 MiB
random_04 AC 5 ms 0.71 MiB
small_00 AC 2 ms 0.71 MiB

#include <cstdio> #include <queue> #include <cmath> #include <cstdint> using namespace std; const uint32_t primemax=31622; vector<uint32_t> primes; uint32_t lpf[primemax+1]; void prec_primes(){ if(lpf[0]) return; lpf[0]=1; fill(lpf+1, lpf+primemax+1, 0); primes.reserve(1.25506*primemax/logl(primemax)); for(uint32_t i=2; i<=primemax; i++){ if(lpf[i]==0){ lpf[i]=i; primes.push_back(i); } for(uint32_t j=0; j<primes.size() and primes[j]<=lpf[i] and primes[j]*i<=primemax; j++) lpf[primes[j]*i]=primes[j]; } } uint32_t euler_totient(uint32_t n){ uint32_t ret=n; for(auto i: primes){ if(i*i>n) break; if(n%i==0){ ret=ret/i*(i-1); do{ n/=i; }while(n%i==0); } } if(n>1) ret=ret/n*(n-1); return ret; } uint32_t modex(uint32_t a, uint32_t b, uint32_t m){ uint32_t ret=1; for(;b;b>>=1, a=(uint64_t)a*a%m){ if(b&1) ret=(uint64_t)ret*a%m; } return ret; } uint32_t tetration_mod(uint32_t a, uint32_t b, uint32_t m){ if(m==1) return 0; if(b==1) return a%m; if(b==0) return 1; if(a==0) return ~b&1; if(a==1) return 1; if(b==2) return modex(a, a, m); if(a==2){ if(b==3) return 16%m; if(b==4) return 65536%m; } auto rec=euler_totient(m); return modex(a, tetration_mod(a, b-1, rec)+rec, m); } int main(){ prec_primes(); uint32_t t; scanf("%u", &t); while(t--){ uint32_t a, b, m; scanf("%u%u%u", &a, &b, &m); printf("%u\n", tetration_mod(a, b, m)); } }