ABC186E

from ABC186 ABC186E

E - Throne
要するに $S + K n \equiv 0 (mod N)$ となるnを求めよという問題
- n = -S / Kすればいい
- mod Nなので割り算には逆元の計算が必要
Kのmod Pでの逆元を求めれば良い
- が、普段使ってたフェルマーの小定理を使うコードはPが素数でない時に正しくない値を返す
- サンプルに入ってた3のmod 10での逆元がまさにこれ。1になってしまう。
- 本当は7: $3 \times 7 = 21 \equiv 1 (mod 10)$
拡張ユークリッド互除法を使って逆元を求める
この場合もKとPが互いに素であることが必要なので、先にgcdして1でないなら割っておく
- Sを割り切れない時は解なし python

def solve(N, S, K):
    from math import gcd
    g = gcd(K, N)
    if g > 1:
        if S % g != 0:
            return -1
        N //= g
        K //= g
        S //= g

    invK = mod_inverse_ee(K, N)
    ret = (N - S) * invK % N

    return ret