bouzuya.hatenablog.com

ぼうずやのにっき

第八回 アルゴリズム実技検定 (PAST) D - 約数を解いた

第八回 アルゴリズム実技検定 (PAST) D - 約数を解いた。

https://atcoder.jp/contests/past202109-open/tasks/past202109_d

X と Y のそれぞれの約数の個数を求めて比較して出力する。

約数の列挙については 2020-04-06 で書いた。整数 N の約数列挙は 1 から √N までの整数 i で試し割りすれば良い。 N を i で割り切れる場合は i と N / i を追加する。 i * i = N のときに二重で追加しないよう注意する。 O(√N) 。

X, Y <= 10^6 なので間に合う。

今日のコミット。