きろく

特筆すべき記録のまとめ

Chokudai SpeedRun 002:J - GCD β

問題

atcoder.jp

解法

最初のペア (A_0, B_0) のどちらかを選ぶかによって作れる GCD の最大値は一意に定まる.具体的には,A_0 を選んだ場合,その次のペアにおいては gcd(A_0, A_1) と gcd(A_0, B_1) のうち大きくなる方を選んだ方が自明に良いので,最初に一つ選び,そこから先は GCD が max となる方を貪欲に選んでいくのがよい.これによって答えの候補が 2 つ得られるので,この 2 つの max を答えとすればよい.O(Nlog(max(A, B))).

解答

atcoder.jp

f:id:babcs2035:20190525162016p:plain