Programacion, ACM ICPC, UVa Online Judge

El link del problema es el siguiente:
12465 – The Turanga Leela Problem

El problema es de Teoría de números.
Dados un numero A y un numero B, tenemos que decir cuantos números tienen en común tal que su residuo sea el mismo.
Para este problema podemos utilizar lo siguiente:
Hacemos una representación de A y B de la forma siguiente:
A = m*(Qa) + r
B = m*(Qb) + r

Donde m es uno de los posibles divisores del numero A y B, y como queremos que el residuo sea el mismo lo representamos para los dos como r.
Después podemos despejar la r en ambas ecuaciones e igualarlas lo que hará que nos quede lo siguiente:
A-B = m(Qa-Qb)

Como todos son números enteros y no hay residuo implicado, implica que “m” divide a A-B. Por lo tanto solo tenemos que encontrar a los divisores de A-B.
Para calcular solo el numero de divisores, se puede hacer simplemente una factorización prima, y con eso obtenemos el numero de veces que aparece un factor. El numero de divisores se puede calcular como:
 Donde p[i] es el exponente de los factores primos.
Ejemplo:
100 205

Su diferencia es 205-100 = 105
El 105 se puede descomponer en primos como la multiplicación de 3x5x7
Como verán el 3 aparece 1 vez, el 5 una vez y el 7 una vez, que son los exponentes.
El numero de divisores esta dado por
(1+1)*(1+1)*(1+1) = 2*2*2 = 8

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: