P16263 [蓝桥杯 2026 省 Python B 组] 密室逃脱开关谜题

你被困在一个密室中，面前有一个控制面板，上面有 $n$ 个开关，控制着密室中的 $m$ 盏灯。开关编号为 $0, 1, \dots, n - 1$，灯编号为 $0, 1, \dots, m - 1$。 开关与灯的作用规则如下： - 按下第 $i$ 个开关（$0 \leq i < n$），会切换第 $(i \bmod m)$ 盏灯和第 $(2 \times i \bmod m)$ 盏灯的状态。 - 如果这两个编号相同（即 $i \bmod m = 2 \times i \bmod m$），则只切换这一盏灯的状态； - 切换指：如果灯是关闭的则打开，如果是打开的则关闭。 初始时，所有灯都处于关闭状态。你可以按任意次开关，每个开关可以被多次按下（也可以不按）。 你的目标是让所有灯最终都变为打开的状态。现在，请你计算：最少需要按多少次开关才能做到这一点；如果无论如何操作都无法让所有灯同时打开，则输出 $-1$。

第一行包含一个整数 $t$，表示测试数据组数。 接下来 $t$ 组数据，每组数据占一行，包含两个整数 $n$ 和 $m$，分别表示开关的数量和灯的数量。

对于每组数据，输出一行，包含一个整数，表示最少需要按开关的次数。如果无法让所有灯都打开，输出 $-1$。

### 【样例说明】 第一组数据：有 $4$ 个开关（编号 $0$ - $3$）和 $4$ 盏灯（编号 $0$ - $3$）。 开关控制关系： - 开关 $0$：控制灯 $0$（同一盏）； - 开关 $1$：控制灯 $1$ 和灯 $2$； - 开关 $2$：控制灯 $2$ 和灯 $0$； - 开关 $3$：控制灯 $3$ 和灯 $2$. 一种最优方案：按开关 $1$、开关 $2$、开关 $3$，共按 $3$ 次。状态变化如下（关 $= 0$，开 $= 1$）： | 状态 | 控制灯 | 灯 $0$ | 灯 $1$ | 灯 $2$ | 灯 $3$ | |:------------:|:------:|:------:|:------:|:------:|:------:| | 初始状态 | | 关 | 关 | 关 | 关 | | 按开关 $1$ | 灯 $1,2$ | 关 | 开 | 开 | 关 | | 按开关 $2$ | 灯 $2,0$ | 开 | 开 | 关 | 关 | | 按开关 $3$ | 灯 $3,2$ | 开 | 开 | 开 | 开 | 第二组数据：有 $5$ 个开关（编号 $0$ - $4$）和 $5$ 盏灯（编号 $0$ - $4$）。 开关控制关系： - 开关 $0$：控制灯 $0$（同一盏）； - 开关 $1$：控制灯 $1$ 和灯 $2$； - 开关 $2$：控制灯 $2$ 和灯 $4$； - 开关 $3$：控制灯 $3$ 和灯 $1$； - 开关 $4$：控制灯 $4$ 和灯 $3$。 一种最优方案：按开关 $0$、开关 $1$、开关 $4$，共按 $3$ 次。状态变化如下： | 状态 | 控制灯 | 灯 $0$ | 灯 $1$ | 灯 $2$ | 灯 $3$ | 灯 $4$ | |:------------:|:------:|:------:|:------:|:------:|:------:|:------:| | 初始状态 | | 关 | 关 | 关 | 关 | 关 | | 按开关 $0$ | 灯 $0$ | 开 | 关 | 关 | 关 | 关 | | 按开关 $1$ | 灯 $1,2$ | 开 | 开 | 开 | 关 | 关 | | 按开关 $4$ | 灯 $4,3$ | 开 | 开 | 开 | 开 | 开 | ### 【评测用例规模与约定】 对于 $20\%$ 的数据：$1 \leq t \leq 3$，$1 \leq n, m \leq 8$； 对于 $50\%$ 的数据：$1 \leq t \leq 3$，$1 \leq n, m \leq 20$； 对于 $80\%$ 的数据：$1 \leq t \leq 5$，$1 \leq n, m \leq 100$； 对于 $100\%$ 的数据：$1 \leq t \leq 5$，$1 \leq n, m \leq 1000$。