Submit Info #2029

Problem Lang User Status Time Memory
Tetration Mod cpp maroonrk AC 257 ms 0.72 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.67 MiB
example_01 AC 1 ms 0.67 MiB
max_00 AC 38 ms 0.68 MiB
max_01 AC 47 ms 0.67 MiB
max_02 AC 45 ms 0.68 MiB
max_1000000000_00 AC 18 ms 0.72 MiB
max_1000000000_01 AC 16 ms 0.72 MiB
max_1000000000_02 AC 15 ms 0.68 MiB
max_998244353_00 AC 257 ms 0.72 MiB
max_998244353_01 AC 253 ms 0.71 MiB
max_998244353_02 AC 249 ms 0.68 MiB
random_00 AC 33 ms 0.72 MiB
random_01 AC 11 ms 0.72 MiB
random_02 AC 5 ms 0.67 MiB
random_03 AC 13 ms 0.67 MiB
random_04 AC 25 ms 0.68 MiB
small_00 AC 2 ms 0.68 MiB

#include <bits/stdc++.h> using namespace std; using ll=long long; #define int ll #define rng(i,a,b) for(int i=int(a);i<int(b);i++) #define rep(i,b) rng(i,0,b) #define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--) #define per(i,b) gnr(i,0,b) #define pb push_back #define eb emplace_back #define a first #define b second #define bg begin() #define ed end() #define all(x) x.bg,x.ed #ifdef LOCAL #define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl #else #define dmp(x) void(0) #endif template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;} template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;} template<class t> using vc=vector<t>; template<class t> using vvc=vc<vc<t>>; using pi=pair<int,int>; using vi=vc<int>; template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p){ return os<<"{"<<p.a<<","<<p.b<<"}"; } template<class t> ostream& operator<<(ostream& os,const vc<t>& v){ os<<"{"; for(auto e:v)os<<e<<","; return os<<"}"; } #define mp make_pair #define mt make_tuple #define one(x) memset(x,-1,sizeof(x)) #define zero(x) memset(x,0,sizeof(x)) #ifdef LOCAL void dmpr(ostream&os){os<<endl;} template<class T,class... Args> void dmpr(ostream&os,const T&t,const Args&... args){ os<<t<<" "; dmpr(os,args...); } #define dmp2(...) dmpr(cerr,"Line:",__LINE__,##__VA_ARGS__) #else #define dmp2(...) void(0) #endif using uint=unsigned; using ull=unsigned long long; template<class t,size_t n> ostream& operator<<(ostream&os,const array<t,n>&a){ return os<<vc<t>(all(a)); } template<int i,class T> void print_tuple(ostream&,const T&){ } template<int i,class T,class H,class ...Args> void print_tuple(ostream&os,const T&t){ if(i)os<<","; os<<get<i>(t); print_tuple<i+1,T,Args...>(os,t); } template<class ...Args> ostream& operator<<(ostream&os,const tuple<Args...>&t){ os<<"{"; print_tuple<0,tuple<Args...>,Args...>(os,t); return os<<"}"; } void print(ll x,int suc=1){ cout<<x; if(suc==1) cout<<"\n"; if(suc==2) cout<<" "; } ll read(){ ll i; cin>>i; return i; } vi readvi(int n,int off=0){ vi v(n); rep(i,n)v[i]=read()+off; return v; } template<class T> void print(const vector<T>&v,int suc=1){ rep(i,v.size()) print(v[i],i==int(v.size())-1?suc:2); } string readString(){ string s; cin>>s; return s; } template<class T> T sq(const T& t){ return t*t; } //#define CAPITAL void yes(bool ex=true){ #ifdef CAPITAL cout<<"YES"<<endl; #else cout<<"Yes"<<endl; #endif if(ex)exit(0); } void no(bool ex=true){ #ifdef CAPITAL cout<<"NO"<<endl; #else cout<<"No"<<endl; #endif if(ex)exit(0); } void possible(bool ex=true){ #ifdef CAPITAL cout<<"POSSIBLE"<<endl; #else cout<<"Possible"<<endl; #endif if(ex)exit(0); } void impossible(bool ex=true){ #ifdef CAPITAL cout<<"IMPOSSIBLE"<<endl; #else cout<<"Impossible"<<endl; #endif if(ex)exit(0); } constexpr ll ten(int n){ return n==0?1:ten(n-1)*10; } const ll infLL=LLONG_MAX/3; #ifdef int const int inf=infLL; #else const int inf=INT_MAX/2-100; #endif int topbit(signed t){ return t==0?-1:31-__builtin_clz(t); } int topbit(ll t){ return t==0?-1:63-__builtin_clzll(t); } int botbit(signed a){ return a==0?32:__builtin_ctz(a); } int botbit(ll a){ return a==0?64:__builtin_ctzll(a); } int popcount(signed t){ return __builtin_popcount(t); } int popcount(ll t){ return __builtin_popcountll(t); } bool ispow2(int i){ return i&&(i&-i)==i; } int mask(int i){ return (int(1)<<i)-1; } bool inc(int a,int b,int c){ return a<=b&&b<=c; } template<class t> void mkuni(vc<t>&v){ sort(all(v)); v.erase(unique(all(v)),v.ed); } ll rand_int(ll l, ll r) { //[l, r] #ifdef LOCAL static mt19937_64 gen; #else static random_device rd; static mt19937_64 gen(rd()); #endif return uniform_int_distribution<ll>(l, r)(gen); } template<class t> int lwb(const vc<t>&v,const t&a){ return lower_bound(all(v),a)-v.bg; } int totient(int m){ int res=m; for(int i=2;i*i<=m;i++){ if(m%i==0){ res=res/i*(i-1); while(m%i==0)m/=i; } } if(m>1) res=res/m*(m-1); return res; } int tetration_sub(int a,int b,int m){ if(b==0)return 1; if(a<=1||m==1)return a; auto mult=[&](int x,int y){ int z=x*y; return z-max(z-m,int(0))/m*m; }; int w=tetration_sub(a,b-1,totient(m)); int res=1; dmp2(a,b,m); dmp(w); while(w){ if(w&1)res=mult(res,a); a=mult(a,a); w>>=1; } dmp(res); return res; } //0<=a //0<=b //1<=m //全部 10^9 オーダー int tetration(int a,int b,int m){ if(a==0)return (b+1)%2%m; return tetration_sub(a,b,m)%m; } signed main(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20); int t;cin>>t; rep(_,t){ int a,b,m;cin>>a>>b>>m; print(tetration(a,b,m)); } }