「BZOJ3884」 上帝与集合的正确用法

Description

求 (large{2^{2^{2^{2^{cdots}}}} mod p}) 的值。

共 (T) 组测试数据。

Hint

(1le Tle 10^3,1le ple 10^7)

Solution

首先，我们有 扩展欧拉定理：

(large{a^b equiv egin{cases} a^{bmod varphi(p) + varphi(p)} & b > varphi(p) \ a^b end{cases} pmod p})

那么，对于 (b > varphi(p)) ，原式就等于：

(large{2^{[(2^{2^{2^{cdots}}}) mod varphi(p) +varphi(p)]}})

然后显然这就是一个递归式子，直接计算即可。当 (p=1) 时，停止递归。

超时？不存在的。

由于 (p > varphi(p)) 所以这个 (p) 会一直减小，直到为 (1)。

并且减小的非常快。

于是就通过了此题。

Code

/*
 * Author : _Wallace_
 * Source : https://www.cnblogs.com/-Wallace-/
 * Problem : BZOJ3884 上帝与集合的正确用法
 */
#include<cstdio>
#include<algorithm>
using namespace std;

const int N=1e7+5;
int phi[N];

void init_phi(int n) {
	phi[1]=1;
	for(register int i=2;i<=n;i++) if(!phi[i])
		for(register int j=i;j<=n;j+=i) {
			if(!phi[j]) phi[j]=j;
			phi[j]=phi[j]/i*(i-1);
		}
}

long long fp(long long a,long long b,long long c) {
	if(!b) return 1ll%c;
	long long t=fp(a,b>>1,c);
	if(b&1) return t*t%c*a%c;
	else return t*t%c;
}

long long solve(int p) {
	return (p==1)?0ll:fp(2,solve(phi[p])+phi[p],p);
}

signed main() {
	init_phi(1e7);
	int T; scanf("%d",&T);
	while(T--) {
		int p; scanf("%d",&p);
		printf("%lld
",solve(p));
	}
}