AtCoder 版！マスター・オブ・整数 (最大公約数編) - Qiita

今回は最大公約数について特集します！ 最大公約数は、初等整数論の醍醐味をたっぷりと味わえる題材です。競プロをやっている方だけでなく、大学受験を志す方にも有益なものが満載です。 (なお、最近の Qiita スマホ表示の不具合により、スマホでは数式がうまく表示されない可能性があります) 0. はじめに 今回は AtCoder の整数問題の中でも特に多い最大公約数に関する知見をまとめます。今回も前回と同様、登場するアルゴリズム自体はたった 1 個です。 Euclid の互除法 Euclid の互除法とは、二つの整数 $a, b$ の最大公約数を求めるアルゴリズムです。たったそれだけなのですが、最大公約数については考えることがものすごく沢山あります。前回の素因数分解と同様、最大公約数も 単にアルゴリズムを覚えるだけでなく、最大公約数という概念について深く理解すること がとても重要だと思います。最大