> makibishi throw|

ABC186E - Throne

問題概要

リンク

円周上にNN個の椅子がある。

椅子の 1 つは王座であり、高橋君は王座のSS個隣に座っている。 高橋君は、今座っている場所からKK個隣の椅子に座る、という行動を繰り返し続ける。 高橋君は王座に座ることができるか?座れる場合、何回目の行動で王座に座ることができるか?

TT個のテストケース全てに答えよ。

制約

1T1001 \leq T \leq 100

2N1092 \leq N \leq 10^9

1SN1 \leq S \leq N

1K1091 \leq K \leq 10^9

解法

愚直にシミュレーションを行うことを考える。KK個先に移動するという行動なので、任意の椅子から移動できる椅子は一意である。よって「王座に移動できない = 王座に座る前にすでに座ったことがある椅子に移動する」といえるためO(N)O(N)で解くことができる。しかし最悪の場合のN=109N=10^9の場合で TLE になってしまうため、より少ない計算量で解く必要がある。

ここで、王座に座った時の行動回数をxxとして他の変数との関係を考えてみる。高橋君は初めSSの位置にいて、KK個隣の椅子に移動することを繰り返すので、最終的な位置は(Kx+S)modN(Kx+S) {\rm mod } Nの椅子である。この椅子が王座であれば良く、王座は高橋君が最初に座っていた椅子のSS個前の椅子なので、SS=0S-S=0番目の椅子である。よって

Kx+S0(modN)\begin{array}{cc} Kx+S \equiv 0 & ({\rm mod } N) \end{array} KxS(modN)\begin{array}{cc} Kx \equiv -S & ({\rm mod } N) \end{array}

が成り立ち、この方程式を解けばxxを求めることができる。

この式は、適当な数a,b,ca,b,cを使って以下のように書くこともできる。

Kx+aN=S+bNKx +aN = -S +bN Kx+(ab)N=SKx +(a-b)N = -S Kx+cN=1(S)(1)\begin{array}{ccc} Kx +cN = 1 \cdot (-S) & \cdots & (1) \end{array}

この式の両辺を、S-Sで割る。(x=xSx^{\prime} = \frac{x}{-S}である。cNcNの項はccで吸収。)

Kx+cN=1Kx^{\prime} +cN = 1

このような、Ax+By=1Ax+By=1を満たすx,yx,yを求めるという問題は、拡張ユークリッドの互除法により解くことができる。 拡張ユークリッドの互除法は正確にはAx+By=gcd(A,B)Ax+By={\rm gcd}(A,B)を満たすx,yx,yを求めるアルゴリズムなので、A,BA,Bが互いに素である必要がある。元々考えていた問題ではA,BA,BがそれぞれK,NK,Nに当たるが、一旦K,NK,Nが互いに素と仮定して話を進める。xx^{\prime}と(使わないが)ccを求めることができた。

求めるxxx=xSx^{\prime} = \frac{x}{-S}よりx=x(S)x = x^{\prime} \cdot (-S)となるため、これで問題を解くことができる。

これでKKNNが互いに素である場合の答えを求めることができたが、

  • 素でない場合は?
  • 王座に到達できない場合の検出方法は?

という 2 つの疑問が残る。これは同時に解決することができる。

G=gcd(K,N)G={\rm gcd}(K,N)とすると、k=KGk=\frac{K}{G}n=NGn=\frac{N}{G}はどちらも整数になり、しかもk,nk,nは互いに素である。

(1)式でs=SGs=\frac{S}{G}となる整数ssが存在すれば、両辺をGGで割り

KGx+cNG=1(SG)\frac{K}{G}x +c\frac{N}{G} = 1 \cdot (-\frac{S}{G}) kx+cn=1(s)kx +cn = 1 \cdot (-s)

と変形することで先の手順でxxを求めることができる。一方s=SGs=\frac{S}{G}となる整数ssが存在しない場合、KKの逆元(xx^{\prime}に当たる)が存在しないので解なしとなる。