[AtCoder] ABC 186 E – Throne

2020年12月20日2021年1月21日

問題

方針

王座の座席番号を \( 0 \) とします。移動した回数を \( x \) と置くと、\( x \) 回移動したときの座席の位置は \( (S + Kx) \bmod N \) となるので、

\[ (S + Kx) \bmod N = 0\]

を求めます。上式は、

\begin{eqnarray}
(S + Kx) \bmod N &=& 0\\
Kx \bmod N &=& -S \bmod N\\
Kx \bmod N &=& (N -S) \bmod N
\end{eqnarray}

となるので、

\[ Kx \bmod N = N – S \]

と変形できます。したがって、\( g = \gcd(K, N) \) として、\( (N – S) \bmod g \neq 0 \) のときは解が存在しません。詳しくは下記の記事を参照してください。

\( (N – S) \bmod g = 0 \) のときを考えます。このとき、\( S + Kx \) は \( N \) の倍数なので、整数 \( y \) を用いて、

\[ S+ Kx = Ny\]

と表せます。また、自然数 \( p, q, r \) (\( p, q\) は互いに素)と \( g = \gcd(K, N) \) を用いて、

\begin{eqnarray}
S+ Kx &=& Ny\\
-Kx + Ny = S\\
g(-px + qy) = gr\\
-px + py = r
\end{eqnarray}

となるので、\( px + qy = 1 \) を満たす整数 \( x, y \) を \((x, y) = (x_0, y_0) \) と見つけたとき、整数 \( t \) を用いて、

\[ x = x_0 + qk\]

と表すことができます。ここで、\( x < 0 \) を満たす \( px + py = r \) の解を \( (x, y) = (x_1, y_1) \) としたとき、

\begin{eqnarray}
gr(px_1 + qy_1) &=& gr\\
Kx_1 + Ny_1 &=& S\\
K(-x_1) + S &=& Ny_1 \\
(S + K(-x_1)) \bmod N &=& 0
\end{eqnarray}

となるので、\( x = -x_1 \) は、\( (S + Kx) \bmod N = 0\) の解となります。また、

\begin{eqnarray}
Kx \bmod N &=& N – S\\
\dfrac{Kx}{g} \bmod \dfrac{N}{g} &=& \dfrac{N – S}{g}\\
\end{eqnarray}

となるので、

\[p = \dfrac{K}{g}, q = \dfrac{N}{g}, r = \dfrac{N – S}{g}\]

とすると、

\[ p(-x_1) \bmod q = r bmod q\]

となるので、\( -x_1 \bmod q \) が答えとなります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll gcd(ll m, ll n) {
  if (n == 0) return m;
  else return gcd(n, m % n);
}

ll extgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll d = extgcd(b, a % b, y, x); 
    y -= a / b * x;
    return d;
}

int main() {
        int T;
    cin >> T;
    ll N, S, K;
    while (T--) {
        cin >> N >> S >> K;
        ll g = gcd(K, N);
        if (g > 1 && (N - S) % g != 0) {
            cout << "-1\n";
        } else {
            ll x, y;
            ll p = K / g;
            ll q = N / g;
            extgcd(p, q, x, y);
            if (x > 0) {
                x = x - (-x / q + 1) * q;
            }
            //cout << x << "\n";
            x = -x * (S / g);
            cout << x % q << "\n";
        }
    }
    return 0;
}

参考