問題概要
リンク
円周上にN個の椅子がある。
椅子の 1 つは王座であり、高橋君は王座のS個隣に座っている。
高橋君は、今座っている場所からK個隣の椅子に座る、という行動を繰り返し続ける。
高橋君は王座に座ることができるか?座れる場合、何回目の行動で王座に座ることができるか?
T個のテストケース全てに答えよ。
制約
1≤T≤100
2≤N≤109
1≤S≤N
1≤K≤109
解法
愚直にシミュレーションを行うことを考える。K個先に移動するという行動なので、任意の椅子から移動できる椅子は一意である。よって「王座に移動できない = 王座に座る前にすでに座ったことがある椅子に移動する」といえるためO(N)で解くことができる。しかし最悪の場合のN=109の場合で TLE になってしまうため、より少ない計算量で解く必要がある。
ここで、王座に座った時の行動回数をxとして他の変数との関係を考えてみる。高橋君は初めSの位置にいて、K個隣の椅子に移動することを繰り返すので、最終的な位置は(Kx+S)modNの椅子である。この椅子が王座であれば良く、王座は高橋君が最初に座っていた椅子のS個前の椅子なので、S−S=0番目の椅子である。よって
Kx+S≡0(modN)
Kx≡−S(modN)
が成り立ち、この方程式を解けばxを求めることができる。
この式は、適当な数a,b,cを使って以下のように書くこともできる。
Kx+aN=−S+bN
Kx+(a−b)N=−S
Kx+cN=1⋅(−S)⋯(1)
この式の両辺を、−Sで割る。(x′=−Sxである。cNの項はcで吸収。)
Kx′+cN=1
このような、Ax+By=1を満たすx,yを求めるという問題は、拡張ユークリッドの互除法により解くことができる。
拡張ユークリッドの互除法は正確にはAx+By=gcd(A,B)を満たすx,yを求めるアルゴリズムなので、A,Bが互いに素である必要がある。元々考えていた問題ではA,BがそれぞれK,Nに当たるが、一旦K,Nが互いに素と仮定して話を進める。x′と(使わないが)cを求めることができた。
求めるxはx′=−Sxよりx=x′⋅(−S)となるため、これで問題を解くことができる。
これでKとNが互いに素である場合の答えを求めることができたが、
- 素でない場合は?
- 王座に到達できない場合の検出方法は?
という 2 つの疑問が残る。これは同時に解決することができる。
G=gcd(K,N)とすると、k=GK、n=GNはどちらも整数になり、しかもk,nは互いに素である。
(1)式でs=GSとなる整数sが存在すれば、両辺をGで割り
GKx+cGN=1⋅(−GS)
kx+cn=1⋅(−s)
と変形することで先の手順でxを求めることができる。一方s=GSとなる整数sが存在しない場合、Kの逆元(x′に当たる)が存在しないので解なしとなる。