[R73E]跳跳棋 - 代码源竞赛平台

时空限制

2S/512M

题目描述

一个圆形刻度盘上有 $m$ 个位置，依次编号为 $0,1,\ldots,m-1$。刻度盘上放有两枚不同的棋子 $A,B$，初始时分别位于不同的位置 $a,b$。

一次操作中，你可以选择其中一枚棋子，以另一枚棋子为中心，将它移动到关于另一枚棋子对称的位置。具体地：

• 若选择棋子 $A$，则令 $a:=(2b-a)\bmod m$；
• 若选择棋子 $B$，则令 $b:=(2a-b)\bmod m$。

其中，$x\bmod m$ 表示与 $x$ 模 $m$ 同余且位于 $[0,m-1]$ 内的唯一整数。

你可以进行任意次操作。求交换两枚棋子位置所需的最少操作次数，即使棋子 $A$ 最终位于初始位置 $b$，且棋子 $B$ 最终位于初始位置 $a$。若无法完成交换，输出 $-1$。

格式

输入格式

本题有多组测试数据。

第一行包含一个正整数 $T$，表示测试数据的组数。

接下来 $T$ 行，每行包含三个整数 $m,a,b$，表示刻度盘的位置数以及两枚棋子的初始位置。

输出格式

对于每组测试数据，输出一行一个整数，表示交换两枚棋子位置所需的最少操作次数。若无法完成交换，输出 $-1$。

样例

样例输入 #1

5
6 0 2
10 1 3
8 1 5
9 2 5
7 0 1

样例输出 #1

3
5
-1
3
7

样例解释 #1

对于第一组测试数据，一种最优操作过程为

$$(0,2)\to(4,2)\to(4,0)\to(2,0)。$$

因此最少需要进行 $3$ 次操作。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$T\le$	$m\le$	特殊性质
$1$	$30$	$10$	$100$	无
$2$			$10^5$
$3$	$20$	$10^5$	$10^9$	特殊性质 A
$4$				无

特殊性质 A：$m$ 为质数。

对于 $100\%$ 的数据，满足 $1\le T\le 10^5$，$2\le m\le 10^{9}$，$0\le a,b<m$，且 $a\ne b$。