Cómo resolver para n, es decir, numerador en UVa 11327

Answer 1

A partir de su código, puedo ver que ya descubrió una forma de encontrar un denominador de esta fracción, utilizando la función phi de Euler.

Ahora enfrenta problemas para encontrar el numerador … Simplemente puedo decirle que ejecutar todos los valores posibles uno por uno y verificar gcd es lo suficientemente rápido como para obtener AC 🙂 Aquí hay un código: http://pastebin.com/YZwVF9Ua.

Sin embargo, supongo que después de implementar la primera parte de la solución de manera inteligente, también está buscando algo mejor para la segunda parte, ¿verdad?

Podemos usar la búsqueda binaria aquí. Está interesado en encontrar el número K-ésimo que es coprimo con N. Digámoslo de una manera diferente: ¿cuál es la X más pequeña de modo que haya al menos K enteros en el rango [1..X] que sean coprimos con N? Ahora debería ser más claro cómo abordarlo con búsqueda binaria. De alguna manera contará buenos números en el rango [1..X], y luego, dependiendo de que este número sea menor o no menor que K, actualizará los límites de la búsqueda binaria.

La última parte es aprender que “de alguna manera” 🙂 Una forma común de resolver este tipo de problemas es el principio de inclusión-exclusión. Usted está interesado en los números, que no son divisibles por ninguno de los divisores primos de N. Digamos que N es divisible por 2, 3 y 5. Entonces el resultado es X – X / 2 – X / 3 – X / 5 + X / 6 + X / 10 + X / 15 – X / 30. Tiene X / 2 allí, porque esa es la cantidad de enteros no mayores que X son divisibles por 2. Lo mismo para X / 3 y X / 5. Pero si algún número es divisible entre 2 y 3, lo ha restado dos veces, por lo que debe volver a sumar esos números … Al extender esta lógica, puede encontrar el principio de inclusión-exclusión usted mismo, incluso si no está familiarizado con eso. O simplemente puede leer sobre esto en Wiki: Principio de inclusión-exclusión (y el primer ejemplo es similar a nuestra tarea).

Usando el principio de inclusión-exclusión, puede calcular el resultado para una X fija simplemente pasando sobre todas las combinaciones de divisores primos de N. 2 * 3 * 5 * 7 * 11 * 13 * 17 ya es más de 200000, por lo tanto, N nunca tendrá más de 6 divisores primos distintos, por lo tanto, tendrá que verificar como máximo 64 máscaras de primos. Aquí hay un código: http://pastebin.com/4vc2XUAf. Puede mejorarlo aún más precalculando productos fuera de la búsqueda binaria y precalculando el número de bits establecidos para todas las máscaras.