Componenti connessi del grafico su $ [n] $ in cui $ i, j $ sono collegati se $ mathrm {gcd} (i, j)> g $

Question

Di recente mi è stata posta la seguente domanda:

Un set di $ N $ Cities è numerata da 1 a $ n $. Dato un numero intero positivo $ g $, due città sono collegate se il loro più grande divisore comune è maggiore di $ g $. Il numero $ n $ può essere grande quanto $ 10^5 $.

Alice ha un elenco di $ Q $ Cities che vorrebbe visitare. Dato l'elenco di Alice di $ Q $ Origin Cities e $ Q $ Destination Cities, restituisci un vettore booleano con un 1 nella posizione $ i $ th indicando che è possibile raggiungere la città di destinazione $ i $ thing dalla $ i $ th città e 0 in caso contrario. La durata dell'elenco $ Q $ può essere grande anche come $ 10^5 $.

Ho risolto questo problema con una soluzione di tempo quadratico. Tuttavia, il grande limite superiore per $ n $ e $ q $ implica chiaramente che esiste un runtime migliore. Tuttavia, non ho ancora visto un modo per accelerare la creazione del grafico.

La mia soluzione crea il grafico in tempo quadratico, usando a UNION TROVA Struttura dei dati per gestire la fusione del componente e l'algoritmo di Euclide per il calcolo dei GCD.

La domanda fondamentale è se esiste un algoritmo $ o $ o (n^2) $ per costruire e interrogare un grafico non diretto, quando i bordi sono definiti da una regola a coppie e sembra che ogni coppia $ (i, j) $ per $ 1 leq i, j leq n $ deve essere esaminato.