Reducir Integer fracciones Algoritmo

Question

(Esto se deriva de una competición de programación recientemente terminado)

Se le da dos conjuntos de 10^5 enteros en el rango 1..10^7 inclusive:

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

Imagine que el número racional X sea el resultado de multiplicar todos los elementos de N y dividir por todos los elementos de D.

Modifique las dos matrices sin cambiar el valor de X (y sin asignar ningún elemento fuera de rango) que el producto de N y el producto de D no tienen commo n factor.

Una solución ingenua (creo) que funcionaría sería ...

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

... pero esto es demasiado lento.

¿Cuál es una solución que requiere menos de alrededor de 10^9 operaciones?

Answer 1

factorizar todos los números en el rango de 1 a 10 . Usando una modificación de un Tamiz de Eratóstenes, puede factorizar todos los números del 1 al n en O(n*log n) vez (creo que es un poco mejor, O(n*(log log n)²) más o menos) usando el espacio O(n*log log n). Mejor que eso, probablemente esté creando una matriz de los factores primos más pequeños.

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

factorizar un número n > 1 usando ese tamiz, buscar su pequeño factor primordial p, determinar su multiplicidad en la factorización de n (ya sea por buscar de forma recursiva, o simplemente dividiendo hasta p no lo hace de manera uniforme brecha el cofactor restante, que es más rápido depende) y el cofactor. Mientras que el cofactor es mayor que 1, busca el siguiente factor primo y repite.

crear un mapa a partir de los números primos de números enteros

ir a través de ambas matrices, para cada número en N, agregue el exponente de cada primo en su factorización al valor en el mapa, por los números en D, restar.

pasar por el mapa, si el exponente del primer es positivo, introduzca p^exponent a la matriz N (puede que tenga que dividir que la mayoría de los índices si el exponente es demasiado grande, y para valores pequeños, combinar varios números primos en una entrada - hay números primos 664579 menores que 10 , así que las 100,000 ranuras en las matrices pueden no ser suficientes para almacenar cada primo que aparece con la potencia correcta), si el exponente es negativo, haga lo mismo con la matriz D, si es 0, ignora ese primo.

Cualquier ranura no utilizada en N o D se establece en 1.

Answer 2

Lets factorize prime cada elemento en N & D en O (sqrt (10^7) * 10^5) como

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

Mantener 2 arrays poder donde

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

Factorice cada elemento de cualquiera de las matrices, ordene, cancele. La factorización es un tiempo constante para las entradas de tamaño limitado, la clasificación es n log n y la cancelación será lineal. Los factores constantes pueden ser grandes, sin embargo.

Si está intentando obtener un tiempo de ejecución real más bajo en lugar de una menor complejidad asintótica, probablemente no sería malo preprocesar las matrices cancelando manualmente factores pequeños, como potencias de 2, 3, 5 y 7. Con alta probabilidad (es decir, a excepción de las entradas patológicas), esto acelerará la mayoría de los algoritmos inmensamente, a costa de unos pocos pases de tiempo lineal.

Un método más sofisticado, la integración de los enfoques anteriores, sería comenzar por la construcción de una lista de números primos hasta sqrt(10^7) ~= 3162. Debería haber aproximadamente 3162/ln(3162) ~= 392 tales primos, por el teorema del número primo. (De hecho, para ahorrar tiempo de ejecución, puede/debe precomputar esta tabla.)

Luego, para cada entero como en N, y para cada primo, reduzca el número entero por ese primo hasta que ya no se divida de manera uniforme, y cada vez incremente un conteo para ese primo. Haga lo mismo para D, disminuyendo en su lugar. Una vez que haya pasado por la tabla de números primos, la int actual será no-1 si y solo si es una primo mayor que 3162. Esto debería ser aproximadamente el 7% del total de enteros en cada matriz. Puede mantener estos en un montón o algo así. Póngalos también en los que están en la matriz, a medida que avanza.

Finalmente, itere sobre los factores positivos y coloque su producto en N. Probablemente necesite dividir esto en varias ranuras de matriz, lo cual está bien. Pon los factores negativos en D, ¡y listo!

El tiempo de ejecución en esto me tomará un minuto para hacer ejercicio. Con suerte, es razonable.

Answer 4

Casi todo ha sido escrito, sugeriría Sea P = (multiplicación de todos los elementos en N)
dejar que q = (multiplicación de todos los elementos en D)
X = (p/q); debe ser constante siempre
buscar los factores primos de p, q;
almacenando posiblemente su potencia en una matriz a [0] (potencia de 2), una [1] (potencia de 3), una [2] (potencia de 5) y así sucesivamente. ahora puede comparar los valores en la matriz y disminuir la potencia de la inferior a cero.
por ejemplo. p = 1280 q = 720
para p a [0] = 8 (potencia de 2) a [1] = 0 (potencia de 3) a [2] = 1 (potencia de 5);
para q b [0] = 4 b [1] = 2 b [2] = 1;

hacer uno/ambos (en caso de que ambos son iguales) valor/s cero para el índice de 0,1,2 .......