超-4运算在 Z/nZ 上的收敛性 – 欧拉函数与扩展欧拉定理

扩展欧拉定理揭示了对于任意模数 $n$，有
$$
a^b\bmod n=\begin{cases}
a^b,&b<\varphi(n)\\
a^{b\bmod \varphi(n)+\varphi(n)},&\text{otherwise}
\end{cases}.
$$

我们又知道若分解质因数 $x=\sum p_i^{c_i}$，则 $\varphi(x)=x\prod (p_i-1)/p_i$。则若 $x>1$，若 $2\mid x$，$\varphi(x)\leq x/2$；否则，$2\mid\varphi(x)$。记 $\varphi^{(k)}(x)=\underbrace{\varphi(\varphi(\cdots\varphi(}_{k\text{ layers}}x)\cdots))$，则 $\newcommand\bigO{\operatorname{O}}\bigO(\log n)$ 级别的 $k$ 就能使其收敛到 $1$。

因此对于 $\mathbb{Z}/n\mathbb{Z}$ 上的超-4运算 $a_1^{a_2^{a_3^{⋰}}}$，结合扩展欧拉定理得到，在指数塔的 $\bigO(\log n)$ 层就将得到 $\bmod\varphi(1)+\varphi(1)\equiv 1$ 的指数。从而它是收敛的。

洛谷题库 P3747 [六省联考 2017] 相逢是问候

一道可以此解决的构造题 – MOCK PTS 20231127 A

给出 $T$ 组询问，$T\leq 1000$。每次给定正整数 $a,m\leq 10^9$，求出一个 int64_t 范围内的正整数 $x$，满足 $a^x\equiv x\pmod m$。

令 $k$ 是极小的满足 ${^k{a}}\equiv{^{k-1}{a}}\pmod m$ 的整数。如果 ${^{k-1}{a}}$ 在 $\mathbb Z$ 上不超过范围限制，我们直接输出即可。

否则，若 $x={^k{a}}$，由扩展欧拉定理及题目原式，它须满足
$$
\begin{aligned}
{^{k+1}{a}}&\equiv{^{k}{a}}\pmod{m}\\
{^k{a}}&\equiv{^{k-1}a}\pmod{\varphi(m)}
\end{aligned}
$$
（由于 ${^{k-1}a}$ 在 $\mathbb Z$ 上远超 $\varphi(m)$，故只需保证 ${}\bmod{\varphi(m)}$ 意义下相同即可。）

因此我们求出 ${}\bmod m, {}\bmod{\varphi(m)}$ 意义下的 ${^{k}a}$，使用扩展中国剩余定理合并两方程（根据结果反推得 exCRT 必然成立）就得到 ${}\bmod\operatorname{lcm}(m,\varphi(m))$ 意义下的 $x$，它符合范围要求。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>
using namespace std;

#define inl inline
typedef long long ll;
typedef unsigned long long ull;
// typedef __int128 lll;
// typedef long double llf;
typedef pair <int, int> pint;
#define fst first
#define scd second
#define all(p) begin (p), end (p)
#define empb emplace_back

int T, a, m;
unordered_map <int, int> rec;

inl int phi (int m) {
	int &x = rec[m];
	if (x) return x;
	else x = 1;
	for (int p = 2; p * p <= m; ++p) {
		if (m % p) continue;
		while (m % p == 0)
			m /= p, x *= p;
		x /= p, x *= p - 1;
	}
	if (m > 1) x *= m - 1;
	return x;
}
inl ll fpow (ll a, ll b, const int mod) {
	ll c = 1; a %= mod;
	for (; b; b >>= 1) {
		if (b & 1) (c *= a) %= mod;
		(a *= a) %= mod;
	}
	return c;
}
int tetra (int a, int b, int m) {
	static int _x;
	if (!b) return _x = 1, 1 % m;
	const int p = phi (m);
	int x = tetra (a, b - 1, p);
	if (_x == -1 || _x >= p)
		x = fpow (a, x + p, m);
	else x = fpow (a, x, m);
	return _x == -1 || pow (a, _x) > INT_MAX ? -1 : fpow (a, _x, INT_MAX), x;
}
inl ll exgcd (ll a, ll b, ll &x, ll &y) {
	if (!b) return x = 1, y = 0, a;
	ll d = exgcd (b, a % b, y, x);
	return y -= a / b * x, d;
}

inl int f (int a, int m) {
	int l = 1, r = 60, mid;
	while (l < r) {
		mid = l + r >> 1;
		if (tetra (a, mid, m) == tetra (a, mid - 1, m)) r = mid;
		else l = mid + 1;
	}
	return l;
}

int main () {
	/*  */
scanf ("%d", &T);
while (T--) {
	scanf ("%d%d", &a, &m);
	int t = f (a, m),
		x1 = tetra (a, t, m),
		x2 = tetra (a, t, phi (m));
	ll u, v, d = exgcd (m, phi (m), u, v);
	const ll p = (ll) m * phi (m) / d, q = (x2 - x1) / d;
	ll y = ((__int128_t) u * q * m + x1) % p + p;
	printf ("%lld\n", y);
}

	return 0;
}

另一种解法

我们试图求 $ka^x\equiv x\pmod m$ 的一个解。

令 $x=p\varphi(m)+r$，则
$$
\begin{aligned}
ka^{[p\geq 1]\varphi(m)}a^r&\equiv p\varphi(m)+r\pmod m\\
\Longrightarrow p\varphi(m)+qm&=ka^{[p\geq 1]\varphi(m)}a^r-r
\end{aligned}
$$

上式有解的充分必要条件是 $\gcd(m,\varphi(m))\mid ka^{[p\geq 1]\varphi(m)}a^r-r$，也即 $ka^{[p\geq 1]\varphi(m)}a^r\equiv r\pmod{\gcd(m,\varphi(m))}$。不难发现，我们总可以调整系数 $p,q$ 使 $p\geq 1$；于是令 $k’=ka^{\varphi(m)},x’=r,m’=\gcd(m,\varphi(m))$，递归解决子问题。边界是 $m=1$ 时 $x=0$。