#P12540. [XJTUPC 2025] 离散对数

    ID: 14093 远端评测题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 4 上传者: 标签>数学2025Special JudgeO2优化高校校赛

[XJTUPC 2025] 离散对数

题目描述

给定正整数 aa, cc, pp,保证 pp 是素数,求 bb 使得:

abbc(modp)a^b \equiv b^c \pmod{p}

我们称整数 A,B,CA, B, CAB(modC)A \equiv B \pmod{C},当且仅当存在整数 kk 使得 AB=C×kA - B = C \times k

输入格式

输入仅一行三个整数 aa, ccpp (1a,c<p1091 \leq a, c < p \leq 10^9),由一个空格隔开,含义如题面所述。

数据保证 pp 是素数。

输出格式

输出仅一个整数 bb (1b10181 \leq b \leq 10^{18}),如果有多个合法答案,你可以输出任意一个。

可以证明,在范围内至少存在一个解。

3 5 7
16
14530529 19260817 19491001 
5660025

提示

对于第一组样例,我们有:

316165(mod7)3^{16} \equiv 16^5 \pmod{7}

因为:

316mod7=43046721mod7=43^{16} \bmod 7 = 43046721 \bmod 7 = 4 165mod7=1048576mod7=416^5 \bmod 7 = 1048576 \bmod 7 = 4