Chokudai SpeedRun002 J. GCD β

問題

整数のペアがN組あり、i番目の整数のペアは(Ai, Bi)で与えられる。
すぬけくんは各ペアからちょうど1つずつ整数を選んで、選んだN個の整数の最大公約数として考えられる最大値が何になるか知りたい。

制約

• 1 <= N <= 5*10^4
• 1 <= Ai, Bi <= 10^9

解法

最初にA1かB1の約数の集合を考えると、A2かB2の約数の集合と共通する約数のみを残していくイメージをすると、どんどん集合サイズが減っていくイメージになる。
なので、結局、最初のA1かB1の約数の集合が最大サイズで、この約数だけが答えの候補になっている。
10^9以下の整数の最大の約数の数を持つものでも1344個程度(高度合成数)しかないので、A1とB1の約数を列挙して合わせて、その約数から条件を満たせるものを選べばよい。