提高-⏱ 1000ms💾 256MB#P7070

题目描述

给定质数 $p$、底数 $a$ 和目标 $b$,求最小的非负整数 $x$ 使 $a^x \equiv b \pmod{p}$。保证有解。

输入格式

一行三个整数 a, b, p。

输出格式

一行一个整数。

数据范围

$$2 \le p \le 10^9 质数,\ 1 \le a < p,\ 0 \le b < p$$

样例输入 #1
2 1 5
样例输出 #1
0
样例输入 #2
2 3 5
样例输出 #2
5