Chokudai SpeedRun 002:J - GCD β
問題
解法
最初のペア (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))).