(Это получено из недавно завершенного соревнования по программированию)

Вам даны два массива по 10 ^ 5 дюймов в диапазоне 1..10 ^ 7 включительно:

int N[100000] = { ... }
int D[100000] = { ... }

Представьте, что рациональное число X будет результатом умножения всех элементов N и деления на все элементы D.

Измените эти два массива, не изменяя значение X (и не назначая какой-либо элемент вне диапазона), чтобы произведение N и произведение D не имели общего множителя.

Наивное решение (я думаю) сработало бы ...

for (int i = 0; i < 100000; i++)
    for (int j = 0; j < 100000; j++)
    {
        int k = gcd(N[i], D[j]); // euclids algorithm

        N[i] /= k;
        D[j] /= k;
    }

... но это слишком медленно

Какое решение требует менее 10-9 операций?