E - Throne
- 拡張ユークリッドの互除法による逆元計算
- 中国剰余定理
  - 実装

E - Throne

問題へのリンク

$S + m \times K \equiv 0 \pmod N$ を満たす最小の整数 $m$ を求めよ。

拡張ユークリッドの互除法による逆元計算

まず、与式を $m \equiv -S \times K^{-1} \pmod N$ と変形することで $K^{-1} \pmod N$ が求まれば、問題を解くことができるとわかります。

ここで、 $\pmod N$ における $K$ の逆元の存在条件は、 $N$ と $K$ が互いに素であることです。

NとKが互いに素のとき

$N$ と $K$ が互いに素のとき、 $K$ の逆元 $K^{-1} \pmod N$ は、拡張ユークリッドの互除法(extGCD)によって求まります。

拡張ユークリッドの互除法による逆元の求め方

$aK + bN = 1$ を満たす整数 $(a, b)$ をextGCDによって求め、この式を $\pmod N$ の式に変形すると、 $aK = 1 \pmod N$ となることから、 $K^{-1} = a$ つまり、aが $K$ の逆元になっています。

NとKが互いに素でないとき

$N$ と $K$ が互いに素ではない場合、 $K$ の逆元 $K^{-1} \pmod N$ は存在しません。では、今回の問題を解くことはできないのでしょうか。サンプルをみればわかる通り、そういうわけではありません。

$N$ と $K$ が互いに素でないなら、互いに素にしたくなります。 $N$ と $K$ を、 $g = gcd(N, K)$ で割った結果をそれぞれ $N^{\prime}, K^{\prime}$ とおくと、 $N^{\prime}$ と $K^{\prime}$ は互いに素です。

これら $N^{\prime}$ と $K^{\prime}$ をextGCDにかけることで、 $K^{\prime -1} \pmod {N^{\prime}}$ を求めることができました。

与式に戻り $N,K,S$ をそれぞれ $N^{\prime}, K^{\prime}, \frac{S}{g}$ に置き換え、

$\frac{S}{g} + m \times K^{\prime} \equiv 0 \pmod {N^{\prime}}$

とすれば、 $\frac{S}{g}$ が整数、すなわち $S$ が $g$ の倍数である場合に、先ほどextGCDによって求めた $K^{\prime -1} \pmod {N^{\prime}}$ を用いて $m$ を求めることができます。

$S$ が $g$ の倍数ではない場合、解はありません。

実装

提出へのリンク

long long extGCD(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long x2, y2;
    long long d = extGCD(b, a%b, x2, y2);
    x = y2;
    y = x2 - (a / b) * y2;
    return d;
}
long long mod_inv(long long a, long long m){
    ll x, y;
    ll d = extGCD(a, m, x, y);
    if(d != 1)return -1;
    if(x < 0)x += m; 
    return x;
}
long long safe_mod(long long a, long long m){
    return (a%m+m)%m;
}
void solve(){
    ll N, S, K;
    cin >> N >> S >> K;
    ll g = gcd(N, K);
    ll inv = mod_inv(K/g, N/g);
    if(S % g != 0){
        cout << -1 << endl;
    }
    else{
        ll ans = S/g * (-inv);
        ans = safe_mod(ans, N/g);
        cout << ans << endl;
    }
}