题解：P12540 [XJTUPC 2025] 离散对数
2672434062xzl
·
·
题解
a^b \equiv b^c \pmod{p}
不妨令 b \equiv a \pmod{p}，则 a^b \equiv a^c \pmod{p}，因为 p 是质数，且 a<p，所以 a 与 p 互质，根据费马小定理 a^{p-1} \equiv 1\pmod{p}，可得 b \equiv c \pmod{p-1}。
所以
b \equiv a\pmod{p}\\
b \equiv c \pmod{p-1}
\end{cases}
$p\equiv 1 \pmod{p-1}$，所以 $p$ 在模 $p-1$ 意义下的逆元为 $1$。
又因为 $p$ 与 $p-1$ 互质，根据中国剩余定理（CRT），答案即为 $(a(p-1)^2+c\cdot p) \mod{p(p-1)}$。
其中 $p(p-1)$ 接近 $10^{18}$，中间运算可能超过 `long long`，需用 `__int128`。
参考代码：
```cpp
#include<iostream>
using namespace std;
using ll=long long;
using lll=__int128;
int main(){
ll a,c,p;
cin>>a>>c>>p;
lll mod=p*(p-1);
cout<<ll((lll(a)*(p-1)%mod*(p-1)+lll(c)*p)%mod);
}
```