(Wynika to z niedawno zakończonego konkursu programistycznego)

Otrzymujesz dwie tablice 10 ^ 5 intów w zakresie 1..10 ^ 7 włącznie:

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

Wyobraź sobie, że wymierna liczba X jest wynikiem mnożenia wszystkich elementów N i podzielenia przez wszystkie elementy D.

Zmodyfikuj dwie tablice bez zmiany wartości X (bez przypisywania żadnego elementu poza zakresem), tak aby iloczyn N i iloczynu D nie miały wspólnego czynnika.

Naiwnym rozwiązaniem (jak sądzę) byłoby działanie ...

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;
    }

... ale to jest za wolne.

Co to jest rozwiązanie, które zajmuje mniej niż około 10 ^ 9 operacji?