离散对数（固定模数）

【题目描述】

给定一个素数 $P$ 及其一个原根 $g$，以及 $n$ 个正整数 $\lbrace a_i\rbrace_{i=0}^{n-1}$，对每个 $a_i$ 输出满足 $g^{b_i}\equiv a_i\pmod P$ 的最小非负整数 $b_i$。

【输入】

$P$ $g$ $n$
$a_0$
$a_1$
:
$a_{n-1}$

【输出】

$b_0$
$b_1$
:
$b_{n-1}$

【输入样例】

998244353 3 6
1
3
9
27
578373382
100

【输出样例】

0
1
2
3
100
500620418

【数据范围】

• $2\le P\le10^9$
• $P$ 是素数
• $1\le n\le10^6$
• $1\le a_i<P$

【来源】

Library Checker（yosupo06） discrete_logarithm_fixed_mod