#1649. 离散对数

离散对数

题目描述

给定素数 p p T T 次询问使得 a,b a, b 满足 axb(modp) a^x \equiv b \pmod p 的最小非负整数 x x

输入格式

第一行包括两个正整数 T T p p

接下来 T T 行,每行包括两个正整数,表示一组询问。

输出格式

输出共 T T 行,每行包括一个非负整数,表示这个最小的 x x ,无解输出 1 -1

样例

15 83
32 20
55 48
76 65
14 38
57 43
24 59
47 27
6 28
18 30
1 82
44 27
40 42
47 78
77 45
52 62
55
24
54
60
13
42
70
8
12
-1
2
-1
60
-1
69

数据范围与提示

对于 20%20\% 的数据,p<103p < 10^3

对于 40%40\% 的数据,p<108p < 10^{8}

对于 60%60\% 的数据,p<1012p < 10^{12}

对于 80%80\% 的数据,p<1018p < 10^{18}

对于 100%100\% 的数据,1T200,2p<3×10181 \le T \le 200, 2 \leq p < 3 \times 10^{18}p p 为素数。