Submit Info #5908

Problem Lang User Status Time Memory
Tetration Mod cpp (anonymous) AC 32 ms 0.72 MiB

ケース詳細
Name Status Time Memory
example_00 AC 3 ms 0.67 MiB
example_01 AC 2 ms 0.68 MiB
max_00 AC 11 ms 0.72 MiB
max_01 AC 9 ms 0.67 MiB
max_02 AC 9 ms 0.67 MiB
max_1000000000_00 AC 2 ms 0.68 MiB
max_1000000000_01 AC 7 ms 0.72 MiB
max_1000000000_02 AC 6 ms 0.67 MiB
max_998244353_00 AC 32 ms 0.72 MiB
max_998244353_01 AC 31 ms 0.72 MiB
max_998244353_02 AC 31 ms 0.71 MiB
random_00 AC 6 ms 0.71 MiB
random_01 AC 8 ms 0.68 MiB
random_02 AC 2 ms 0.68 MiB
random_03 AC 5 ms 0.71 MiB
random_04 AC 6 ms 0.67 MiB
small_00 AC 0 ms 0.68 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; if(n % 2 == 0){ res = res / 2; while(n % 2 == 0) n /= 2; } if(n % 3 == 0){ res = res / 3 * 2; while(n % 3 == 0) n /= 3; } for(unsigned int i = 5; i * i <= n; i += 4){ if(n % i == 0){ res = res / i * (i - 1); while(n % i == 0) n /= i; } i += 2; 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 long long a, unsigned int b, unsigned int mod, bool flag) { unsigned long long res = 1; while(b){ if(b & 1){ if((res *= a) >= mod) res %= mod, flag = true; } if((a *= a) >= mod) a %= mod, flag = true; b >>= 1; } return res + (flag ? mod : 0); } unsigned int rec(unsigned int a, unsigned int b, unsigned int mod) { if(a == 0) return !(b & 1); if(a == 1 || mod == 1) return 1; if(b == 1) return (a >= mod) ? (a % mod + mod) : a; if(b == 2) return mod_pow(a % mod, a, mod, (a >= mod)); const unsigned phi_val = phi(mod); const unsigned int res = rec(a, b-1, phi_val); return mod_pow(a % mod, res, mod, (res >= phi_val)); } unsigned int tetration(unsigned int a, unsigned int b, unsigned int mod) { if(b == 0) return (mod != 1); const unsigned int res = rec(a, b, mod); return (res >= mod) ? (res - mod) : res; } 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; }