Автокомментарий: текст был обновлен пользователем omoyamo (предыдущая версия, новая версия, сравнить).

Auto comment: topic has been translated by omoyamo (original revision, translated revision, compare)

What is the source of this problem?

What is the range of the integers in the array?

I don't know exact time complexity, but use treap, where every node maintains '2D-Persistent tree with FFT on each node'. To further optimization use meet-in-the-middle, but I don't know how to merge, but at all you can create a graph, after that go to Dominator tree and do some stuffs with combinatorics or Burnside's lemma. But I don't know time complexity.

I don't have an exact time complexity, but I think I do have a few steps towards a solution.

First let's make a segment tree of sets. Since it doesn't help to have multiple of a single number, we can operate on those sets instead of the raw array.

Second, let's compensate for the GCD by getting the maximum 2-3 LCM's. This should be safe because GCD is almost always small relative to LCM.

Now, how do we find the largest LCM quickly from a set of numbers? I suggest we simply run two for loops, each starting from the large end of the set, and calculate the LCMs. Importantly, we should short-circuit when we cannot possibly find a larger LCM later in the loop.

If we consider the first run of the outer loop, either we find some LCM greater than the largest number in the set, or it we don't. If we don't then we know all the rest of the numbers are factors of this one, so there is a small number of them and our loops will be short. If we don't, then we have some larger number as out biggest current LCM. Each inner loop can them be short circuited when the two elements multiplied is smaller than that LCM.