AtCoder ABC 186 E - Throne

ABC 186のEがさっぱりだったので復習。

問題

N個の座席が円周状に並んでいて、1つは玉座
初期位置は玉座から時計回りにS個ずれている
1回の移動で、時計回りにK個ずれる
何回移動すれば玉座に座れる?

以下、座席の位置を0～N-1、玉座を0とする。初期位置はSで、位置0に到達するための回数を求める問題となる。

解法の概略

最大公約数(GCD)で行けるかどうか判定
拡張ユークリッドの互除法(通称extgcd)を用いて逆元を求める
逆元×移動したい個数が答え

最大公約数と移動可能性

NとKの最大公約数(GCD)をgとする。KとNは何倍してもgの倍数なので、ループして戻ってきてもgの倍数ごとの位置となる。すなわち、最小の移動単位がgであることを意味している。
特に、gが1より大きいときについて考えると、g未満のずれを解消することはできないということである。開始位置Sからg単位でしか移動できないので、位置を0にするためにはS % g = 0(Sをgで割った余りが0)でなければならない。
なので、まずNとKの最大公約数gを求め、S % g = 0でなければ不可とし、そうでない場合は、NとKとSをgで割っておく。そうすると以降、NとKは互いに素となるので、扱いやすくなる。

移動回数と周期性

NとKが互いに素のとき、同じ場所に戻ってくる回数について考えてみる。初期位置が0で、a回移動したあとの位置bは、Nごとに1周するのでNの余りとなり、b = (a × K) % Nと表すことができる。同じ場所に戻ってくるのはb = 0、すなわちa × KがNの倍数となるときである。それはNとKの最小公倍数(LCM)ということになるが、NとKは互いに素なので最小公倍数はN × Kである。つまり、N回移動するごとに同じ場所に戻ってくる。(周期Nごとに、N個の異なる位置を取る)

逆元と任意の場所への移動

問題を少し変形して、一つ隣の位置に行くことを考えてみる。もしa回の移動で一つ隣の位置に行けるならば、b個先の位置には、a × b回の移動で行けるはずである。
この問題では位置をNの余りで考えるので、Nを法とする合同式で扱っていることになる。それをmod Nと記述する。このような世界で便利な数に逆元がある。逆元はかけると1になる数であり、x × K ≡ 1 (mod N)となるxが逆元である。これはつまり、x回移動すると位置が1進むことを意味している。すなわち、逆元が求まれば移動回数が計算できそうである。

逆元の計算

ax + by = gcd(a, b)となるx, yは拡張ユークリッドの互除法(通称extgcd)で計算できる。ここではextgcdによりKx + Ny = 1となるx, yを計算する。mod Nで考えるとNyが消えてKx ≡ 1 (mod N)となる。xがmod NにおけるKの逆元であり、x回移動すると一つ隣の位置に行ける。
サンプルにあるN=998244353, S=897581057, K=595591169で逆元を計算すると-145577299となった。ただし求めたいのは正の移動回数なので、これを直接答えには使えない。ここでN回ごとに同じ位置に戻る周期性を利用すると、-145577299 + N = 852667054回の移動で隣に行けることがわかる。

移動回数の計算

初期位置Sから位置0に移動したいので、N - S個移動する。
隣に移動するのに(x + N) % N回必要なので、((x + N) % N) × (N - S)回移動すればよい。さらに、N回ごとに同じ位置に戻るので、答えは((x + N) × (N - S)) % Nとなる。また、N回周期なのでこれが最小値となる。
サンプルにあるN=998244353, S=897581057, K=595591169だと((-145577299 + 998244353) × (998244353 - 897581057)) % 998244353 = 85832276046249984 % 998244353 = 249561088となり出力例と一致した。
よくあるextgcdの実装では戻り値としてgcdを返すので、それを利用するなら以下のようになる。(C++)

long long x, y;
long long g = extgcd(k, n, x, y);
long long ans = (((x + n) * (n - s)) % n) / g;

余談

pが素数のときはフェルマーの小定理から $a^{p - 2}$ mod pでaの逆元が計算できるが、この問題ではNが合成数のこともあるので適用できない。

参考情報

プログラミングコンテストチャレンジブック(蟻本)第2版 p.109
拡張ユークリッドの互除法〜一次不定方程式 ax + by = c の解き方〜