Submit Info #1982

Problem Lang User Status Time Memory
Tetration Mod cpp (anonymous) WA 84 ms 0.68 MiB

ケース詳細
Name Status Time Memory
example_00 AC 5 ms 0.62 MiB
example_01 WA 7 ms 0.67 MiB
max_00 AC 23 ms 0.64 MiB
max_01 AC 22 ms 0.67 MiB
max_02 AC 21 ms 0.63 MiB
max_1000000000_00 AC 12 ms 0.68 MiB
max_1000000000_01 AC 15 ms 0.68 MiB
max_1000000000_02 AC 13 ms 0.63 MiB
max_998244353_00 AC 84 ms 0.64 MiB
max_998244353_01 AC 84 ms 0.68 MiB
max_998244353_02 AC 83 ms 0.62 MiB
random_00 AC 17 ms 0.67 MiB
random_01 AC 9 ms 0.68 MiB
random_02 AC 8 ms 0.65 MiB
random_03 AC 8 ms 0.68 MiB
random_04 AC 14 ms 0.68 MiB
small_00 WA 5 ms 0.62 MiB

#include <bits/stdc++.h> #define ll long long #define INF 1000000005 #define MOD 1000000007 #define EPS 1e-10 #define rep(i,n) for(int i=0;i<(int)(n);++i) #define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i) #define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i) #define each(a,b) for(auto& (a): (b)) #define all(v) (v).begin(),(v).end() #define len(v) (int)(v).size() #define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end()) #define cmx(x,y) x=max(x,y) #define cmn(x,y) x=min(x,y) #define fi first #define se second #define pb push_back #define show(x) cout<<#x<<" = "<<(x)<<endl #define sar(a,n) {cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl;} using namespace std; template<typename S,typename T>auto&operator<<(ostream&o,pair<S,T>p){return o<<"{"<<p.fi<<","<<p.se<<"}";} template<typename T>auto&operator<<(ostream&o,set<T>s){for(auto&e:s)o<<e<<" ";return o;} template<typename S,typename T,typename U> auto&operator<<(ostream&o,priority_queue<S,T,U>q){while(!q.empty())o<<q.top()<<" ",q.pop();return o;} template<typename K,typename T>auto&operator<<(ostream&o,map<K,T>&m){for(auto&e:m)o<<e<<" ";return o;} template<typename T>auto&operator<<(ostream&o,vector<T>v){for(auto&e:v)o<<e<<" ";return o;} void ashow(){cout<<endl;}template<typename T,typename...A>void ashow(T t,A...a){cout<<t<<" ";ashow(a...);} template<typename S,typename T,typename U> struct TRI{S fi;T se;U th;TRI(){}TRI(S f,T s,U t):fi(f),se(s),th(t){} bool operator<(const TRI&_)const{return(fi==_.fi)?((se==_.se)?(th<_.th):(se<_.se)):(fi<_.fi);}}; template<typename S,typename T,typename U> auto&operator<<(ostream&o,TRI<S,T,U>&t){return o<<"{"<<t.fi<<","<<t.se<<","<<t.th<<"}";} typedef pair<int, int> P; typedef pair<ll, ll> pll; typedef TRI<int, int, int> tri; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<vi> vvi; typedef vector<vl> vvl; typedef vector<P> vp; typedef vector<double> vd; typedef vector<string> vs; const int MAX_N = 100005; unsigned int phi(unsigned int n) { unsigned int res = n; for(unsigned 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; } unsigned int mod_pow(unsigned int a, unsigned int b, unsigned int mod) { unsigned int res = 1; while(b){ if(b & 1){ res = (unsigned long long)res * a % mod; } a = (unsigned long long)a * a % mod; b >>= 1; } return res; } unsigned int rec(unsigned int a, unsigned int b, unsigned int mod) { if(a == 1 || b == 0) return 1; if(mod == 1) return 0; unsigned int ans = rec(a, b-1, phi(mod)), ad = mod; if(ans <= 32 && a < mod && pow((double)a, ans) < mod) ad = 0; return mod_pow(a % mod, ans, mod) + ad; } inline unsigned int tetration(unsigned int a, unsigned int b, unsigned int mod) { return rec(a, b, mod) % mod; } int main() { cin.tie(0); ios::sync_with_stdio(false); int T; cin >> T; rep(i,T){ int a, b, c; cin >> a >> b >> c; cout << tetration(a, b, c) << "\n"; } return 0; }