satiseni https://blog.hatena.ne.jp/satiseni/ 幸せに https://satiseni.hateblo.jp/ プログラミング を整数とすると， と互いに素な任意の整数 に対し， を満たす整数 がただ一つ存在します．この を， を法としたときの逆数といい，競技プログラミングで頻繁に役立ちます．今回はこれを計算するコードを C で書いていきます． 数学的な解き方 ならば，ある整数 が存在して です．すると，これは と書き換えられます．ここで を で割った余りを とすると， となります．これを繰り返すことで を求めることができます．具体的には， とするとある が存在して よって あるが存在してよって これより，最後の の値を とすれば，逆に辿って の値を求めることができます．逆に辿るやり方は， より より より より とい… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fsatiseni.hateblo.jp%2Fentry%2F2020%2F02%2F23%2F025957" title="MOD 逆数 - 幸せに" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2020-02-23 02:59:57 rich https://satiseni.hateblo.jp/entry/2020/02/23/025957 1.0 100%