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<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#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));

	}

}