P4139 上帝与集合的正确用法（扩展欧拉定理） 解题笔记

原文创建时间：2021-02-22 18:43:27

题目链接

P4139

题意简述

$T$ 组询问，每次给定模数 $p$，对应求出 $\displaystyle 2^{2^{\cdots^2}}\bmod p$ 的值。

解题笔记—搬运

前置芝士：扩展欧拉定理

$\displaystyle a^b \equiv \begin{cases}a^b & (b < \varphi( p )) \\ a^{b \bmod \varphi( p ) \ + \ \varphi( p )} & (b \geq \varphi( p ))\end{cases} \pmod p$

解

因为幂次是无穷的，所以首先必然会进入 $b \geq \varphi( p )$ 分支。

考察指数。因为 $\forall \ p:1 \leq \varphi( p ) < p$，所以模数必然会在有限次递归后缩小到 $1$。由此，一方面由于模数在不断缩小，$b \geq \varphi( p )$ 必然始终成立；另一方面，易见模数为 $2$ 或 $1$ 时余数为 $0$，故我们设计其作为递归边界。

代码

#include<bits/stdc++.h>
#define REG register

using namespace std;

namespace ACAH
{
	typedef long long ll;
	
	int T;
	ll p;
	
	template<class T> inline void qread(T &x)
	{
		x = 0; REG int t = 0; REG char ch = getchar();
		while(!isdigit(ch)) t |= (ch == '-'), ch = getchar();
		while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
		x = t ? -x : x;
	}
	
	inline ll qpow(ll a, ll x, ll mod)
	{
		REG ll s = a, t = a; --x;
		while(x) {
			if(x & 1) s = s * t % mod;
			t = t * t % mod;
			x >>= 1;
		}
		return s;
	}
	
	inline ll phi(ll x)
	{
		REG ll res = x;
		for(REG ll i = 2; i * i <= x; i++) {
			if(x % i) continue;
			res = res / i * (i - 1);
			while(x % i == 0) x /= i;
		}
		if(x > 1) res = res / x * (x - 1);
		return res;
	}
	
	inline ll solv(ll x)
	{
		if(x <= 2) return 0;
		REG ll ph = phi(x);
		return qpow(2, solv(ph) + ph, x);
	}
	
	int work()
	{
		qread(T);
		while(T--) {qread( p ); printf("%lld\n", p <= 2 ? 0 : solv( p ));}
		return 0;
	}
}

int main() {return ACAH::work();}