2021年 1月 12日
まえがき
丘を超えて ラララ星の彼方 ゆくぞ~ あとむ~
健康管理
何した
今日解いた問題
パナソニックプログラミングコンテスト (ABC186) E-Throne
[拡張ユーグリッド,extgcd,逆元]
S + X * K = α * N (α は1以上の整数)よなるような最小のXを求めよという問題.
X * K ≡ -S (mod N) を解く.みたいなノリっぽいですね.
ここで X ≡ -S * (Kの逆元) として解きたいなあ.みたいな感じなんだけど,ここから先が分からなくて解けなかった.
そのうち理解したくなったら蟻本の260pを見よう♡
ちなみに,逆元に関する知識として,
mod が素数じゃない時は,逆元が存在しないときもあるらしいよ.
素数じゃないときは,互いに素なら存在する.らしい!!!
あとがき
以下は毎回記事に貼っているテンプレート
基本的に読書はTwitterで絡みのある人だけだと思いますが、僕のブログだけ見てるって人もいるかもしれないので、一応自己紹介っぽいことをしている記事を貼っておきます - 瑞々しぃにぼしの自己紹介(自己紹介の記事です)