简要题意
对于给定正整数 \(X\)，求出最小的正整数 \(n\)，使其满足：
\[n^n \equiv X \pmod{10^9}
\]
若没有输出 \(-1\)。保证 \(\gcd(X, 2) = 1\) 且 \(\gcd(X, 5) = 1\)。
分析
\(n\) 的上界达到 \(10^9-1\)，直接枚举不太行。从模数下手，\(10^9 = 2^9 \cdot 5^9\)。思考一件事：\(2^9 = 512, 5^9 = 1953125\) 都不大，可以直接枚举，那我们能否分别求出模 \(2^9\) 和 \(5^9\) 意义下的答案，然后合并呢？
手模 \(n^n\) 在模 \(2\) 意义下为 \(1, 0\) 循环，在模 \(5\) 意义下为 \(1, 4, 2, 1, 0, 1, 3, 1, 4, 0, 1, 1, 3, 1, 0, 1, 2, 4, 4, 0\) 循环（周期 \(20\)）。能否推广到 \(2^9\) 和 \(5^9\) 呢？
:::info[欧拉定理]
若 \(\gcd(a,m) = 1\)，则 \(a^{\varphi(m)} \equiv 1 \pmod{m}\)。
参考资料。
:::
性质一
当 \(a\) 为奇数时：
\[a^a \equiv (a+2^9)^{a+2^9} \pmod{2^9}
\]
:::info[证明]
模意义下简化底数：
\[a \equiv a+2^9 \pmod{2^9}
\]
欧拉定理简化指数：
\[\because \varphi(a^9) = 2^8,
\therefore a^{2^8} \equiv 1 \pmod{2^9}
\]
联立：
\[a^{a+2^9} = a^a \cdot a^{2^9} =a^a \cdot (a^{2^8})^2
\]
代入上式：
\[a^a \cdot (a^{2^8})^2 \equiv a^a \cdot 1 \pmod{2^9}
\]
:::
性质二
当 \(\gcd(a, 5) = 1\) 时：
\[a^a \equiv (a+4 \cdot 5^9)^{a+4 \cdot 5^9} \pmod{5^9}
\]
:::info[证明]
同样简化底数：
\[a \equiv a+4 \cdot 5^9 \pmod{5^9}
\]
同样简化指数：
\[\because \varphi(5^9) = 4 \cdot 5^8, \therefore a^{4 \cdot 5^8} \equiv 1 \pmod{5^9}
\]
联立：
\[a^{a+4 \cdot 5^9} = a^a \cdot a^{4 \cdot 5^9} =a^a \cdot (a^{4 \cdot 5^8})^5
\]
代入上式：
\[a^a \cdot (a^{4 \cdot 5^8})^5 \equiv a^a \cdot 1 \pmod{5^9}
\]
:::
合并
找到 \(u,v\) 满足：
\[u^u \equiv n^n \pmod{2^9}, v^v \equiv n^n \pmod{5^9}
\]
那么：
\[n = 2^9 \cdot k_1 +u = 4 \cdot 5^9 \cdot k_2 + v
\]
复杂度
预处理暴力找完 \(1 \sim 2^9\) 和 \(1 \sim 4 \cdot 5^9\) 的答案，大概做 \(10^7\) 次快速幂。
每次询问暴力枚举 \(k_2\)，每次 \(2^7\) 次验证。
记录。然而 MX 的老爷机直接 TLE，爆零了 /ll。
Code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+5;
int qpow(int x,int y,int mod){int res=1;while(y){if(y&1) res=res*x%mod;x=x*x%mod;y>>=1;}return res;
}
vector<signed> a1[N],a2[N];
signed main(){int m1=1,m2=1;for(int i=1;i<=9;i++)m1*=2,m2*=5;for(int i=1;i<m1;i++){if(i%2==0) continue;int u=qpow(i,i,m1);a1[u].push_back(i);}for(int i=1;i<m2*4;i++){if(i%5==0) continue;int u=qpow(i,i,m2);a2[u].push_back(i);}int T;cin>>T;while(T--){int x;cin>>x;assert(x%2&&x%5);int p=x%m1,q=x%m2,ans=1e9;for(int u:a1[p])for(int v:a2[q]){for(int i=0;i*(m2<<2)+v<1000000000;i++)if((i*(m2<<2)+v-u)%m1==0){ans=min(ans,i*(m2<<2)+v);break;}}cout<<ans<<'\n';}return 0;
}