Round Hopscotch

2 secs 1024 MB
OxOmiso's icon OxOmiso

問題文

座標平面上に,原点を中心とした半径 11 の円があり,円上に NN 個のマスがあります。
(0,1)(0,1) にあるマスをマス 00 として円上に等間隔に時計回りにマス 0,1,2,,N10,1,2, \dots , N-1 が並んでいます。
Alice と Bob ははじめ,それぞれマス A,B  (0A,BN1)A,B \; (0 \leq A,B \leq N-1) にいて,22 人はこれから以下の 移動同時に好きな回数行います。( 11 回も行わなくても構いません)

  • Alice がマス x  (0xN1)x \; (0 \leq x \leq N-1) にいるとき,Alice はマス x+K  (mod  N)x+K \; (mod \; N) に移動する。
  • Bob がマス y  (0yN1)y \; (0 \leq y \leq N-1) にいるとき,Bob はマス y+L  (mod  N)y+L \; (mod \; N) に移動する。

22 人がともにマス 00 にいるようにできるでしょうか。可能ならば必要な 移動 の回数の最小値を,不可能ならばそれを報告してください。

11 回も移動せずとも二人ともマス 00 にいる場合も,移動回数を 00 回として出力することに注意してください。

テストケースが TT ケース与えられるので,全てに答えてください。

想定解に誤りがありました。申し訳ございません。現在は修正されています。(2024/03/16 2:51)

制約

  • 1T21051 \leq T \leq 2*10^5
  • 1N1061 \leq N \leq 10^6
  • 0A,BN10 \leq A,B \leq N-1
  • 1K,LN1 \leq K,L \leq N
  • 入力は全て整数である

入力

TT
N1  A1  B1  K1  L1N_1 \; A_1 \; B_1 \; K_1 \; L_1
N2  A2  B2  K2  L2N_2 \; A_2 \; B_2 \; K_2 \; L_2
\dots
NT  AT  BT  KT  LTN_T \; A_T \; B_T \; K_T \; L_T

出力

i  (1iT)i \; (1 \leq i \leq T) 個目のテストケースについて,22 人がともにマス 00 にいるようにすることが可能ならば,必要な 移動 の回数の最小値を,不可能ならば -1 を,一行に出力してください。改行も忘れないようにしてください。

入力例 11

4
3 1 2 2 1
5 2 3 2 3
31 4 1 5 9
2 0 1 1 1

出力例 11

1
4
24
-1

11 つ目のテストケースについて,11移動 を行うことで,Alice は 1+2=31+2=3 よりマス 00 に,Bob は 2+1=32+1=3 よりマス 00 にいます。00 回では両者がともにマス 00 にいることはできないので,11 を出力します。
22 つ目のテストケースについて,44移動 を行うことで,Alice は 2+24=102+2*4=10 よりマス 00 に,Bob は 3+34=153+3*4=15 よりマス 00 にいます。33 回以下では両者がともにマス 00 にいることはできないので,44 を出力します。
33 つ目のテストケースについて,2424移動 を行うことで,Alice は 4+524=1244+5*24=124 よりマス 00 に,Bob は 1+924=2171+9*24=217 よりマス 00 にいます。2323 回以下では両者がともにマス 00 にいることはできないので,2424 を出力します。
44 つ目のテストケースについて,何回移動しても 22 人がともにマス 00 にいるようにはできないので,-1 を出力します。

Submit


Go (1.21)