题解 | 2023 年牛客多校第九场 B 题题解

题意：给定 $a,ma,m$，构造一个非负整数 $uu$，使得 $a^u\equiv u(\mathrm{m}\mathrm{o}\mathrm{d}m)a^u\; \backslash equiv\; u\; \backslash pmod\; m$。，$0\le u\le 10^{18}0\; \backslash le\; u\; \backslash le\; 10^\{18\}$。多测，$1\le T\le 10^{3}1\; \backslash le\; T\; \backslash le\; 10^3$。

解法：首先定义记号 ${}^{\mathrm{\infty }}a^\backslash infty\; a$ 表示 $a^{a^{a^{\cdots }}}a^\{a^\{a^\backslash cdots\}\}$，即 $aa$ 叠无穷多层指数塔。首先不难注意到一个最简单的性质：

这个数字显然是不可计算的无穷大，但是考虑在模意义下，由于模运算内参与运算的元素个数有限，并且由下面的扩展欧拉定理：

这个 ${}^{\mathrm{\infty }}a^\backslash infty\; a$ 一定在模意义下对应一个唯一确定的整数。下文中讨论 ${}^{\mathrm{\infty }}a^\backslash infty\; a$ 的值，一定是针对于某个特定的模数而言。

由扩展欧拉定理可得，要想求 ${}^{\mathrm{\infty }}a\mathrm{m}\mathrm{o}\mathrm{d}m^\backslash infty\; a\; \backslash bmod\; m$，考虑使用扩展欧拉定理。显然 ${}^{\mathrm{\infty }}a^\backslash infty\; a$ 充分大，因而有：

而对于任意一个数字 $mm$，不断对它求 $\phi (m)\backslash varphi(m)$，不超过 $\mathcal{O}(2\log m)\backslash mathcal\; O(2\; \backslash log\; m)$ 次操作就可以使 $m=1m=1$，这时 ${}^{\mathrm{\infty }}a\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}1)^\backslash infty\; a\; \backslash equiv\; 0\; \backslash pmod\; 1$，因而更高次指数不再有意义，因而可以通过下面的递归函数求出 ${}^{\mathrm{\infty }}a\mathrm{m}\mathrm{o}\mathrm{d}m^\backslash infty\; a\; \backslash bmod\; m$ 的值。本题即P4139 上帝与集合的正确用法。

long long dfs(long long base, long long p)
{
    if (p == 1)
        return 0;
    long long phip = phi(p);
    long long y = power(base, dfs(base, phip) + phip, p);
    return y;
}

下面开始对本题的正式解法描述。

法一：首先考虑 $a^u\equiv u(\mathrm{m}\mathrm{o}\mathrm{d}m)a^u\; \backslash equiv\; u\; \backslash pmod\; m$ 的形式。如果假设 $uu$ 有 $a^{k}a^k$ 形式，则带入可得 $a^{a^k}\equiv a^k(\mathrm{m}\mathrm{o}\mathrm{d}m)a^\{a^k\}\; \backslash equiv\; a^k\; \backslash pmod\; m$。如果这个 $uu$ 充分大（即大于 $\phi (m)\backslash varphi(m)$），则根据扩展欧拉定理的指数条件有 $a^k\equiv k(\mathrm{m}\mathrm{o}\mathrm{d}\phi (m))a^k\; \backslash equiv\; k\; \backslash pmod\{\backslash varphi(m)\}$，而这个式子与原式形式完全相同且模数减小，因而可以考虑一路递归下去，如此进行到 $m=1m=1$。这时考虑边界条件，不妨设此时的 $uu$ 仍然具有 $a^{k}a^k$ 形式，而这显然成立（模 $11$ 意义下什么值都是 $00$）。因而，我们可以假定 $uu$ 就是 ${}^{\mathrm{\infty }}a^\backslash infty\; a$。

由于 ${}^{\mathrm{\infty }}a^\backslash infty\; a$ 对于不同的模数就有不同的值，回到原式考虑这个 $uu$ 需要满足什么条件。显然由最基本的条件，$a^{{}^{\mathrm{\infty }}a}={}^{\mathrm{\infty }}a\equiv u(\mathrm{m}\mathrm{o}\mathrm{d}m)a^\{^\backslash infty\; a\}=\backslash \; ^\backslash infty\; a\; \backslash equiv\; u\; \backslash pmod\; m$。此外，由于它在指数上，因而由 $a^u\equiv {}^{\mathrm{\infty }}a=a^{{}^{\mathrm{\infty }}a}(\mathrm{m}\mathrm{o}\mathrm{d}m)a^u\; \backslash equiv\backslash \; ^\backslash infty\; a=a^\{^\backslash infty\; a\}\; \backslash pmod\; m$ 可得 $u\equiv {}^{\mathrm{\infty }}a(\mathrm{m}\mathrm{o}\mathrm{d}\phi (m))u\; \backslash equiv\backslash \; ^\backslash infty\; a\; \backslash pmod\; \{\backslash varphi(m)\}$。注意这里的 $uu$ 要充分大。因而可以得到如下的同余方程：

因而有 $u\equiv {}^{\mathrm{\infty }}a(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{l}\mathrm{c}\mathrm{m}(m,\phi (m)))u\; \backslash equiv\; \backslash \; ^\backslash infty\; a\backslash pmod\{\{\backslash rm\; lcm\}(m,\; \backslash varphi(m))\}$。考虑直接用上述方程组解 exCRT（扩展中国剩余定理）即可。因为 ${}^{\mathrm{\infty }}a(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{l}\mathrm{c}\mathrm{m}(\phi (m),m))^\backslash infty\; a\; \backslash pmod\{\{\backslash rm\; lcm\}(\backslash varphi(m),\; m)\}$ 一定存在，因而上述同余方程组一定有解。复杂度 $\mathcal{O}\left(T\sqrt{V}\right)\backslash mathcal\; O\backslash left(T\; \backslash sqrt\{V\}\backslash right)$。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
ll mul(ll a, ll b, ll p) {
    ll r = a * b - (ll)((long double)a / p * b + 0.5) * p;
    return r < 0 ? r + p : r;
}
ll fpow(ll a, ll b, ll p, ll x = 1) {
    for (; b; b >>= 1, a = mul(a, a, p))
        if (b & 1) x = mul(x, a, p);
    return x;
}
int phi(int x) {
    int p = x;
    for (int i = 2; i * i <= x; i++) {
        if (x % i) continue;
        p -= p / i;
        while (x % i == 0) x /= i;
    }
    if (x > 1) p -= p / x;
    return p;
}
int A;
ll f(ll x) {
    if (x == 1) return 1;
    ll p = phi(x), lcm = p * x / __gcd(p, x);
    return fpow(A, f(p), lcm) + lcm;
}
void Solve() {
    int x;
    scanf("%d%d", &A, &x);
    ll w = f(x), d = (ll)x * phi(x) / __gcd(x, phi(x));
    printf("%lld\n", w >= 1e18 ? w % d : w);
}
int main() {
    int t = 1;
    scanf("%d", &t);
    while (t--) Solve();
    return 0;
}

法二：首先不难注意到当 $\gcd (a,m)=1\backslash gcd(a,m)=1$ 时，$a^{\phi (m)}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)a^\{\backslash varphi(m)\}\; \backslash equiv\; 1\; \backslash pmod\; m$。如果 $\phi (m)\mathrm{\mid }u\backslash varphi(m)|u$ 且 $u\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)u\; \backslash equiv\; 1\; \backslash pmod\; m$ 有解的时候这样的 $uu$ 就是合法的。可惜这个同余方程组不一定有解。考虑让上述方程有解，即考虑一个一般情况，即 $uu$ 仍然是充分大（大于 $\phi (m)\backslash varphi(m)$）时，有 $a^u\equiv a^c(\mathrm{m}\mathrm{o}\mathrm{d}m)a^u\; \backslash equiv\; a^c\; \backslash pmod\; m$，其中 $cc$ 为一常数且 $c\in [\phi (m),2\phi (m))c\; \backslash in\; [\backslash varphi(m),2\backslash varphi(m))$。则考虑指数和底数条件有：

消去 $uu$ 将同余方程组转化为丢番图方程，观察对 $cc$ 的约束，有：

即 $a^c-c=k_{1}m+k_2\phi (m)a^c\; -c\; =k\_1m+k\_2\backslash varphi(m)$，右侧必为 $g=\gcd (m,\phi (m))g=\backslash gcd(m,\backslash varphi(m))$ 的倍数。由于 $k_1,k_{2}k\_1,k\_2$ 的任意性，右侧可以组合出一切 $gg$ 的倍数，因而有 $a^c\equiv c(\mathrm{m}\mathrm{o}\mathrm{d}g)a^c\; \backslash equiv\; c\; \backslash pmod\; \{g\}$，就可以开始递归计算上述方程 $cc$ 的解。对于每一轮递归，可以考虑暴力回代解出相应的 $uu$。