题解：P12540 [XJTUPC 2025] 离散对数

题目描述

给定正整数

a

c

p

，保证

p

是素数，求

b

使得：

a^b \equiv b^c \pmod{p}

先说结论：直接输出

(p-1)^2

。

\textcolor{white}{(我可以说是瞪眼法吗qaq)}

由费马小定理知，如果

p

是一个质数，而整数

a

不是

p

的倍数，则有：

a^{p-1} \equiv 1 \pmod{p}

这意味着 a 的幂次在模 p 下以 p-1 为周期。

因此，对于任意指数

b

有：

a^b \equiv a^{b \bmod (p-1)} \pmod{p}

我们令

b = (p-1)^2

则有：

\textcolor{white}{(真的是瞪眼法qwq)}

b \equiv 0 \pmod{p-1}

于是：

a^b \equiv a^0 \equiv 1 \pmod{p}

又因为：

b = (p-1)^2 = p^2 - 2 \times p + 1

p^2 \equiv 0 \pmod{p} \\ 2 \times p \equiv 0 \pmod{p} \\ 1 \equiv 1 \pmod{p} \\ \end{cases}$$ 所以： $$ b^c \equiv b \equiv 1 \pmod{p} $$ 显然，当 $b=p-1$ 时 $$ a^b \equiv b^c \pmod{p} $$ 证毕 ## code $\textcolor{white}{(不会真有人不会写吧)}$ ```cpp #include<iostream> using namespace std; long long p;//记得开long long! int main(){ cin>>p>>p>>p;//连a,c都不用读 cout<<(p-1)*(p-1); } ``` [record](https://www.luogu.com.cn/record/217774051)