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

· · 题解

题解：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}{(不会真有人不会写吧)}

#include<iostream>
using namespace std;
long long p;//记得开long long!
int main(){
    cin>>p>>p>>p;//连a,c都不用读
    cout<<(p-1)*(p-1);
}

record