edo1z blog

プログラミングなどに関するブログです

2020-03-17から1日間の記事一覧

C++ 割ったあまり

参考 「1000000007 で割ったあまり」の求め方を総特集! 〜 逆元から離散対数まで 〜 - Qiita 分かりやすいmodの説明動画 www.youtube.com www.youtube.com 基本 掛け算、足し算、引き算は、計算途中で余りだす。 引き算は、余りがマイナスになったらmodを足…

C++ 拡張ユークリッドの互除法

ユークリッドの互除法は2つの自然数の最大公約数を求める際に利用します。 a % b == r の場合、a, bの最大公約数は、b, rの最大公約数と等しいです。 b % r == r2、r % r2 == r3と繰り返すことで、最終的に余りが0になったときの割ってる方の数が最大公約数…