自动搬运

查看原文

来自洛谷，原作者为

	Leasier 我们所知的是沧海一粟，我们所不知的是汪洋大海。

搬运于2025-08-24 22:23:29，当前版本为作者最后更新于2020-07-16 19:33:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Subtask $1$

前置芝士：大步小步算法（BSGS）

由高德纳箭号表示法的定义可得：$a \uparrow b = a^b$。又由于 Subtask $1$ 的保证 $p$ 为质数，所以我们使用 BSGS 求解原方程即可。时间复杂度为 $O(T \sqrt{p} \log p)$。

Subtask $2$

前置芝士：扩展欧拉定理（exEuler）

我们首先来化简 $a \uparrow \uparrow b$。

$a \uparrow \uparrow b = a \uparrow (a \uparrow \uparrow (b - 1))$

$= a^{a \uparrow \uparrow (b - 1)}$

$= a^{a^{a \uparrow \uparrow (b - 2)}}$

$= \cdots$

$= a^{a^{.^{.^{.^a}}}}$（共 $b$ 个 $a$）

预处理欧拉函数的值，然后从 $0$ 开始枚举 $x$ 的值并判断即可。设 $k_1$ 表示使欧拉函数变为 $1$ 的最少嵌套层数 $+ 1$，则 $x$ 的枚举上界为 $k_1$。

这里计算 $a \uparrow \uparrow b$ 时需要用到扩展欧拉定理。但是，由于我们在计算 $a^b \bmod p$ 之类的式子时，需要判断 $b$ 与 $\varphi(p)$ 之间的大小关系，所以我使用了一个名为 Node 的结构体来保存运算结果取模后的值和这个结果取模前是否大于 $\varphi(p)$。时间复杂度为 $O(T \sqrt{p} \log p)$。

Subtask $3$

我们首先来化简 $a \uparrow^3 b$。

$a \uparrow^3 b = a \uparrow \uparrow (a \uparrow^3 (b - 1))$

由于欧拉函数嵌套多层后其值会变为 $1$，所以如果我们要算出 $a \uparrow^3 b \bmod p$ 的值，只要算出 $a \uparrow \uparrow \min(a \uparrow^3 (b - 1), k_1) \bmod p$ 即可。因此，$a \uparrow^3 b$ 可以递归计算。

预处理欧拉函数的值，然后从 $0$ 开始枚举 $x$ 的值并判断即可。$x$ 的枚举上界为满足 $a \uparrow \uparrow (k_2 - 1) \geq k_1$ 的最小 $k_2$。时间复杂度为 $O(T \sqrt{p} \log p)$。

具体细节见代码注释。

代码：

#include <iostream>
#include <map>
#include <cmath>

using namespace std;

typedef long long ll;

typedef struct {
	ll val;
	bool flag;
} Node;

int phi[37];
map<ll, int> mp;

inline Node new_node(ll val, bool flag){
	Node ans;
	ans.val = val;
	ans.flag = flag;
	return ans;
}

inline Node quick_pow(ll x, ll p, ll mod){
	Node ans;
	ans.val = 1;
	ans.flag = false;
	while (p){
		if (p & 1){
			ans.val *= x;
			if (ans.val >= mod){
				ans.val %= mod;
				ans.flag = true;
			}
		}
		p >>= 1;
		if (p == 0) break;
		x *= x;
		if (x >= mod){
			x %= mod;
			ans.flag = true;
		}
	}
	return ans;
}

inline int bsgs(int a, int b, int p){
	if (p == 1) return 0;
	a %= p;
	b %= p;
	if (b == 1) return 0;
	int m = ceil(sqrt(p)), i = 0;
	ll t = quick_pow(a, m, p).val;
	mp.clear();
	for (register ll j = b; i < m; i++, j = j * a % p){
		mp[j] = i;
	}
	i = 1;
	for (register ll j = t; i <= m; i++, j = j * t % p){
		if (mp.count(j)) return i * m - mp[j];
	}
	return -1;
}

inline int euler(int n){
	int ans = n;
	for (register int i = 2; i * i <= n; i++){
		if (n % i == 0){
			ans -= ans / i;
			while (n % i == 0){
				n /= i;
			}
		}
	}
	if (n > 1) ans -= ans / n;
	return ans;
}

Node tetration(int a, int n, int index){
	if (phi[index] == 1) return new_node(0, true);
	if (n == 0) return new_node(1, false);
	int next_index = index + 1;
	Node x = tetration(a, n - 1, next_index);
	if (x.flag) x.val += phi[next_index];
	return quick_pow(a, x.val, phi[index]);
}

inline int f(int a){
	if (a == 1) return 0;
	for (register int i = 0; ; i++){
		if (tetration(a, i, 0).flag) return i + 1;
	}
}

inline ll quick_pow_with_max_val(ll x, ll p, ll max_val){
	ll ans = 1;
	while (p){
		if (x >= max_val){
			return max_val;
		}
		if (p & 1){
			ans *= x;
			if (ans >= max_val){
				return max_val;
			}
		}
		x *= x;
		p >>= 1;
	}
	return ans;
}

ll tetration_with_max_val(ll a, ll n, int max_val){
	if (n == 0 || a == 1) return 1;
	ll x = tetration_with_max_val(a, n - 1, max_val);
	if (x == max_val) return max_val;
	return quick_pow_with_max_val(a, x, max_val);
}

ll pentation_with_max_val(ll a, ll n, int max_val){
	if (n == 0 || a == 1) return 1;
	ll x = pentation_with_max_val(a, n - 1, max_val);
	if (x == max_val) return max_val;
	return tetration_with_max_val(a, x, max_val);
}

inline ll pentation(ll a, ll n, int max_val, ll mod){
	if (mod == 1) return 0;
	if (n == 0) return 1;
	return tetration(a, pentation_with_max_val(a, n - 1, max_val), 0).val % mod;
}

int main(){
	int t;
	cin >> t;
	for (register int i = 1; i <= t; i++){
		int a, n, b, p;
		cin >> a >> n >> b >> p;
		if (n == 1){
			cout << bsgs(a, b, p) << endl;
		} else {
			int maxx_2 = 0, ans = -1;
			for (register int j = p; j != 1; j = euler(j)){
				phi[maxx_2++] = j;
			}
			phi[maxx_2] = 1;
			if (n == 2){
				for (register int j = 0; j <= maxx_2; j++){
					if (tetration(a, j, 0).val == b){
						ans = j;
						break;
					}
				}
			} else {
				int maxx_3 = f(a);
				for (register int j = 0; j <= maxx_3; j++){
					if (pentation(a, j, maxx_2, p) == b){
						ans = j;
						break;
					}
				}
			}
			cout << ans << endl;
		}
	}
	return 0;
}