UOJ Logo Universal Online Judge

UOJ

#603. 【WC2021】斐波那契

统计

众所周知,小葱同学擅长计算,尤其擅长计算组合数。但是对组合数有了充分研究的小葱同学对组合数失去了兴趣,而开始研究数列。

我们定义 $F_0 = a$,$F_1 = b$,$F_i = (F_{i-1} + F_{i-2}) \bmod m$($i \ge 2$)。

现在给定 $n$ 组询问,对于每组询问请找到一个最小的整数 $p$,使得 $F_p = 0$。

输入格式

第一行两个整数 $n, m$,代表询问的组数和每组计算中的模数。

接下来 $n$ 行每行两个整数 $a, b$,代表一组询问中 $F_0$ 和 $F_1$ 的值。

输出格式

对于每组询问,输出一行一个整数 $p$ 代表答案。如果这样的 $p$ 不存在,输出 -1

样例一

input

4 5
0 1
1 2
2 3
3 4

output

0
3
2
-1

样例二

input

1 6
4 4

output

3

样例三

见附加文件中 ex_fib3.inex_fib3.ans

样例四

见附加文件中 ex_fib4.inex_fib4.ans

限制与约定

对于所有测试点:$1 \le n, m \le {10}^5$,$0 \le a, b < m$。

每个测试点的具体限制见下表:

测试点编号 $n, m \le$ 特殊限制
$1 \sim 2$ $1000$
$3 \sim 4$ ${10}^5$ $m$ 是质数
$5 \sim 6$ $m = p_1 p_2 \cdots p_k$,其中 $p_i$ 是两两不同的质数
$7 \sim 10$

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载