数论是一门很棒的学科。在信息学竞赛中，数论算法一直是学习的重点、难点。它的代码实现较为简单，却不容易建立模型求解。因此，多加练习是解决这类题目的好方法。像大牛说的一样，“题做多了，考题都变成原题了”。

一句话题意

\[ 给定正整数p，求2^{2^{2^{2^...}}}（无限个2）mod\ p.\]

解法

首先来介绍一下欧拉函数及欧拉定理。

欧拉函数：设n是一个正整数，欧拉$ \varphi $函数$ \varphi(n) $定义为不超过n且与n互质（也称互素）的正整数的个数。

欧拉定理：设m是一个正整数，a是一个整数且$(a,m)=1 $（即：a, m互质），那么$a^{\varphi(m)}\equiv1(mod\ m) .$

接下来，我们引入扩展欧拉定理：

$${a^x} \equiv {a^{x\bmod \varphi \left( m \right) + \varphi \left( m \right)}}\left( { \bmod m\ } \right),x \ge \varphi \left( m \right).$$

这个定理不要求a和p互质，可以直接使用。

参考证明-来自知乎专栏

回到题目中，设$a=2,n=2^{2^{2^…}} $，由于有无穷个2，

所以有$a^n \bmod p = a^{a^n \bmod \varphi(p) + \varphi(p)}\bmod p$.

可以发现$ a^n \bmod p$和$a^n \bmod \varphi(p)$是一样的，所以我们可以递归求解。

边界条件：当$a^n \bmod p$为定值时结束。我们可以知道当$p=1$时这个式子必然等于0，可以结束。

这样时间复杂度是$ O(\log\ p) $的。这样加上快速幂就能求解了。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
typedef long long ll;
#define R register
#define I inline
//宏定义 
template<class T>void read(T &x) {
	register int c = getchar(), f = 1; x = 0;
	while(!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
	while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
	x *= f;
}
//读入优化 
inline ll qpow(ll x,ll y,ll p)
{
	register ll ans=1;
	while(y)
	{
		if(y&1) ans=ans*x%p;
		x=x*x%p,y>>=1;
	}
	return ans;
}  
inline ll phi(ll x)
{
	register ll i,ans=x;
	for(i=2;i*i<=x;i++)
	{
		if(x%i==0)
		{
			ans=ans/i*(i-1);
			while(x%i==0) x/=i;
		}
	}
	if(x!=1) ans=ans/x*(x-1);
	return ans;
}
inline ll calc(ll p)
{
	if(p==1) return 0;
	register ll res=phi(p);
	return qpow(2,calc(res)+res,p);
}
int main(){
	register int t;
	register ll p;
	read(t);
	for(register int i=1;i<=t;i++)
	{
		read(p);
		printf("%lld\n",calc(p));
	}
	return 0;
}

参考资料

https://www.cnblogs.com/GXZlegend/p/6950483.html

https://blog.csdn.net/popoqqq/article/details/43951401/

https://zhuanlan.zhihu.com/p/24902174