(Dies ist aus einem kürzlich abgeschlossenen Programmierwettbewerb abgeleitet)

Sie erhalten zwei Arrays mit 10 ^ 5 Zoll im Bereich 1..10 ^ 7 einschließlich:

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

Stellen Sie sich vor, die rationale Zahl X sei das Ergebnis der Multiplikation aller Elemente von N und der Division durch alle Elemente von D.

Ändern Sie die beiden Arrays, ohne den Wert von X zu ändern (und ohne ein Element außerhalb des Bereichs zuzuweisen), sodass das Produkt von N und das Produkt von D keinen gemeinsamen Faktor haben.

Eine naive Lösung (glaube ich) wäre ...

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

... aber das ist zu langsam.

Was ist eine Lösung, die weniger als 10 ^ 9 Operationen benötigt?