Description

求出\(k^{k^{k^{k^{...}}}} \pmod p\) 的结果

---

扩展欧拉定理：\[a^x=a^{min(x,x\%\varphi(p)+\varphi(p))}(mod \ p)\]

题中由于是无限层，所以答案就是 \(x\)

由于\(\varphi(\varphi(\varphi(...)))\)总有一次会变成\(1\)的，那时候\(x\%p=0\)

那么就每次递归求解\(x\%\varphi(p)\)这一块就好了啊

---

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define LL long long#define max(a,b) ((a)>(b)? (a):(b))#define min(a,b) ((a)<(b)? (a):(b))using namespace std;LL i,m,n,j,k,a[10001],p,t;LL eular(LL x){    LL now=x, r=sqrt(now);    for(LL i=2;i<=r;i++)     {        if(x%i!=0) continue;        now=now/i*(i-1);        while(x%i==0) x/=i;    }    if(x!=1) now=now/x*(x-1);    return now; }LL quick(LL x,LL m,LL M){    LL t=1;    for(m;m>1;m>>=1, x=x*x%M)         if(m&1) t=t*x%M;    return x*t%M;}LL dfs(LL now){    if(now==1) return 0;    LL phi=eular(now);    return quick(n,dfs(phi)+phi,now);}int main(){    scanf("%lld",&t);    for(t;t;t--)    {        scanf("%lld%lld",&n,&p);        printf("%lld\n",dfs(p));    }}