Submit Info #44537

Problem Lang User Status Time Memory
Tetration Mod cpp ZigZagKmp AC 454 ms 158.66 MiB

ケース詳細
Name Status Time Memory
example_00 AC 213 ms 158.55 MiB
example_01 AC 215 ms 158.55 MiB
max_00 AC 254 ms 158.55 MiB
max_01 AC 251 ms 158.63 MiB
max_02 AC 247 ms 158.59 MiB
max_1000000000_00 AC 222 ms 158.55 MiB
max_1000000000_01 AC 222 ms 158.59 MiB
max_1000000000_02 AC 222 ms 158.66 MiB
max_998244353_00 AC 453 ms 158.55 MiB
max_998244353_01 AC 452 ms 158.59 MiB
max_998244353_02 AC 454 ms 158.55 MiB
random_00 AC 237 ms 158.60 MiB
random_01 AC 221 ms 158.55 MiB
random_02 AC 222 ms 158.63 MiB
random_03 AC 223 ms 158.66 MiB
random_04 AC 232 ms 158.59 MiB
small_00 AC 216 ms 158.55 MiB

#include<bits/stdc++.h> using namespace std; #define maxn 10000005 #define maxm 2000005 #define inf 0x3f3f3f3f #define int long long #define ull unsigned long long #define db double #define ldb long double #define eps 1e-9 #define local void file(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);} template <typename Tp> void read(Tp &x){ int fh=1;char c=getchar();x=0; while(!isdigit(c)){if(c=='-'){fh=-1;}c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c&15);c=getchar();}x*=fh; } int n,mod; int MO(int x,int Mod){return (x<Mod)?x:(x%Mod+Mod);} int ksm(int b,int p=mod-2,int Mod=mod){int ret=1;while(p){if(p&1)ret=MO(1ll*ret*b,Mod);b=MO(1ll*b*b,Mod);p>>=1;}return ret;} int p[maxn],pr[maxn],phi[maxn],tot; void prep(int N){ phi[1]=1; for(int i=2;i<=N;++i){ if(!p[i])pr[++tot]=i,phi[i]=i-1; for(int j=1;j<=tot;++j){ if(i*pr[j]>N)break; p[i*pr[j]]=1; if(i%pr[j])phi[i*pr[j]]=phi[i]*(pr[j]-1); else{ phi[i*pr[j]]=phi[i]*pr[j]; break; } } } } int get_phi(int x){ if(x<=10000000)return phi[x]; int ret=x; for(int i=2;i*i<=x;++i){ if(x%i==0){ while(x%i==0)x/=i; ret=ret/i*(i-1); } } if(x>1)ret=ret/x*(x-1); return ret; } int calc(int b,int p,int Mod){ if(p==1||Mod==1)return MO(b,Mod); int nxtM=get_phi(Mod); return ksm(b,calc(b,p-1,nxtM),Mod); } signed main(){ prep(10000000); int CasT; read(CasT); while(CasT--){ int a,b; read(a);read(b);read(mod); if(b==0){ puts(mod==1?"0":"1"); continue; } if(a==0){ int tans=(b%2==0); printf("%lld\n",tans%mod); continue; } printf("%lld\n",calc(a,b,mod)%mod); } return 0; }