Official

C - LCM of GCDs Editorial by evima


For a fixed pair of \(X\) and \(Y\), it is possible to determine in \(O(N)\) time whether there is a way to put the balls in the bags so that the greatest common divisor of the integers in the red bag is a multiple of \(X\), and the greatest common divisor of the integers in the blue bag is a multiple of \(Y\). Now, let us exhaustively search for \(X\) and \(Y\).

Assume that we put \(a_1\) in the red bag and \(b_1\) in the blue bag. Then, \(X\) and \(Y\) are divisors of \(a_1\) and \(b_i\), respectively, so we just need to try \(d(a_1)d(b_1)\) candidates for \(X\) and \(Y\), where \(d(n)\) is the number of divisors of \(n\).

This approach works in \(O(d(a_1)d(b_1)N)\) time, which is fast enough.

posted:
last update: