最大公約数 (paizaランク C 相当)
素因数分解で最大公約数を求める
今回は素因数分解を用いた最大公約数を求める問題でした。最大公約数は、pythonの組み込み関数gcd()、ユークリッドの互除法でも求められますが、素因数分解を用いても最大公約数が求められます。
与えられる整数ごとに、素因数分解を行い、それぞれの因数が出てくる個数の最小値を求めることで、最大公約数が求められます。しかし、共通の素因数だけでなく、他の整数には含まれていない素因数の数を「0」個として形状しなければうまく答えが導けないので、全ての整数について素因数を求めた後に、各整数に含まれない素因数の個数を「0」として初期化しておくのに苦労しました。
辞書型で素因数と個数を格納する
筆者は、各整数の素因数と個数をそれぞれ辞書型に格納しておき、全ての整数の素因数と個数を求めた後に、keys()を使って一つのkeylistを辞書型で格納しました。そして改めて、各整数の答えの辞書にkeylistの中に含まれない素因数の個数を「0」として追加しておきます。
最小値の配列で素因数の個数の最小値を求める
ここまで準備できれば、後は全ての整数の素因数と個数の最小値を求めるだけですので、minanserという最小値だけを格納する配列を用意して、どれか一つの整数の素因数とこ数の答えで初期化し、残りの整数の答えの最小値を更新することで、求める最大公約数を算出することができるようになります。