Ridurre intere frazioni Algoritmo

Question

(Questo deriva da un concorso di programmazione recentemente completato)

Si sono dati due array di 10^5 interi nel range 1..10^7 compreso:

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

Immaginate che il numero razionale X sia il risultato della moltiplicazione di tutti gli elementi di N e della divisione di tutti gli elementi di D.

Modificare i due array senza modificare il valore di X (e senza assegnare alcun elemento fuori intervallo) come che il prodotto di N e il prodotto di D non hanno commo n fattore.

Una soluzione ingenua (credo) avrebbe funzionato sarebbe ...

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

... ma questo è troppo lento.

Che cos'è una soluzione che richiede meno di circa 10^9 operazioni?

Answer 1

in fattori tutti i numeri nell'intervallo da 1 a 10 . Utilizzando una modifica di un setaccio di Eratostene, è possibile calcolare tutti i numeri da 1 a n nel tempo O(n*log n) (penso che sia un po 'meglio, O(n*(log log n)²) o giù di lì) utilizzando lo spazio O(n*log log n). Meglio di quello è probabilmente la creazione di un array di solo i fattori primi più piccoli.

// Not very optimised, one could easily leave out the even numbers, or also the multiples of 3 
// to reduce space usage and computation time 
int *spf_sieve = malloc((limit+1)*sizeof *spf_sieve); 
int root = (int)sqrt(limit); 
for(i = 1; i <= limit; ++i) { 
    spf_sieve[i] = i; 
} 
for(i = 4; i <= limit; i += 2) { 
    spf_sieve[i] = 2; 
} 
for(i = 3; i <= root; i += 2) { 
    if(spf_sieve[i] == i) { 
     for(j = i*i, step = 2*i; j <= limit; j += step) { 
      if (spf_sieve[j] == j) { 
       spf_sieve[j] = i; 
      } 
     } 
    } 
} 

Per fattorizzare un numero n > 1 utilizzando tale setaccio, guardare in alto il suo fattore primo più piccolo p, determinare la sua molteplicità nella fattorizzazione di n (sia guardando in su in modo ricorsivo, o semplicemente dividendo fino a quando non lo fa in modo uniforme p divide il cofattore rimanente, che è più veloce dipende) e il cofattore. Mentre il cofattore è più grande di 1, cerca il fattore primo successivo e ripeti.

creare una mappa da numeri primi di interi

passare attraverso entrambi gli array, per ogni numero in N, aggiungere l'esponente di ogni primo nella sua fattorizzazione al valore nella mappa, per i numeri in D, sottrarre.

Go attraverso la mappa, se l'esponente del primo è positivo, immettere p^exponent alla matrice N (potrebbe essere necessario dividere che in diversi indici se l'esponente è troppo grande, e per piccoli valori, combinare diversi numeri primi in una voce - ci sono 664579 numeri primi inferiori a 10 , quindi i 100.000 slot negli array potrebbero non essere sufficienti per memorizzare ogni primo apparente con la potenza corretta), se l'esponente è negativo, fare lo stesso con l'array D, se è 0, ignora quel numero primo.

Gli slot inutilizzati in N o D vengono quindi impostati su 1.

Answer 2

Lets primo factorize ogni elemento in N & D a O (sqrt (10^7) * 10^5) come

N[i]=p1^kn1 * p2^kn2 ... 
D[i]=p1^kd1 * p2^kd2 ... 

Mantenere 2 array di alimentazione dove

Power_N[p1]=sum of kn1 for all i's 
Power_D[p1]=sum of kd1 for all i's 

Divide the N and D by p1^(min(Power_N[p1],Power_D[p2])) in O(10^5) each 

Answer 3

Factorize ogni elemento di una matrice, ordinare, annullare. La fattorizzazione è un tempo costante per interi di dimensioni limitate, l'ordinamento è n log n e l'annullamento sarà lineare. I fattori costanti possono essere grandi, però.

Se si sta tentando un tempo di esecuzione effettivo inferiore anziché una minore complessità asintotica, probabilmente non farebbe male preelaborare gli array annullando manualmente piccoli fattori, come i poteri 2, 3, 5 e 7. Con alta probabilità (ad eccezione degli input patologici), questo velocizzerà immensamente la maggior parte degli algoritmi, al costo di pochi passaggi di tempo lineare.

Un metodo più sofisticato, che integra gli approcci di cui sopra, sarebbe iniziare con la costruzione di un elenco di numeri primi fino a sqrt(10^7) ~= 3162. Ci dovrebbero essere circa 3162/ln(3162) ~= 392 tali numeri primi, con il teorema dei numeri primi. (In realtà, per risparmiare tempo in esecuzione, si potrebbe/dovrebbe precompute questa tabella.)

Poi, per ciascun numero intero N, e per ogni primo, ridurre il numero intero da quel primo fino a che non si divide in modo uniforme, e ogni volta incrementa un conteggio per quel primo. Fai lo stesso per D, decrementando invece. Una volta che hai passato la tabella dei numeri primi, l'attuale int sarà non-1 se e solo se è un numero primo maggiore di 3162. Questo dovrebbe essere circa il 7% degli interi totali in ciascun array. Puoi tenerli in un mucchio o somesuch. Impostali anche su quelli dell'array, mentre vai avanti.

Infine, si iterano i fattori positivi e si inserisce il loro prodotto in N. Probabilmente sarà necessario suddividerlo su più slot di array, il che va bene. Metti i fattori negativi in ​​D e il gioco è fatto!

Il tempo di esecuzione su questo mi ci vorrà un minuto per risolvere. Si spera, è ragionevole.

Answer 4

Quasi tutto è stato scritto, suggerirei Sia P = (moltiplicazione di tutti gli elementi in N)
lasciare q = (moltiplicazione di tutti gli elementi in D)
X = (p/q); dovrebbe essere costante sempre
trovare i fattori primi di p, q;
memorizzando eventualmente la loro potenza in una matrice a [0] (potenza di 2), a [1] (potenza di 3), a [2] (potenza di 5) e così via. ora è possibile confrontare i valori nella matrice e diminuire la potenza di quella inferiore a zero.
es. p = 1280 q = 720 per p a [0] = 8 (potenza di 2) a [1] = 0 (potenza di 3) a [2] = 1 (potenza di 5);
per q b [0] = 4 b [1] = 2 b [2] = 1;

fanno uno/due (nel caso entrambi sono uguali) Valore/s zero per indice 0,1,2 .......