Number Theory too.


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 1G

Author:
Problem type
Allowed languages
C, C++, Java, Pascal, Python, VB

Definamos la función \phi(N) como \displaystyle \phi(N)=|\big\{m\in\mathbb{N}|m\leq N \land mcd(m,N)=1\big\}| donde |·| es la cardinalidad del conjunto, o lo que es lo mismo, la cantidad de números enteros i (1 \leq i \leq N) coprimos con N. Dado un entero K diga la cantidad de números enteros positivos N que existen tales que \phi(N)=K.

Restricciones

1 \leq K \leq 2*10^8

Entrada

La entrada consta de una sola línea con un entero K.

Salida

La salida consta de una sola línea con la respuesta al problema dado.

Subtareas

  • Subtarea 1: K es impar (1 punto)
  • Subtarea 2: K\leq5*10^3 (2 puntos)
  • Subtarea 3: K\leq2*10^5 (4 puntos)
  • Subtarea 4: K\leq10^6 (8 puntos)
  • Subtarea 5: K\leq10^7 (16 puntos)
  • Subtarea 6: K\leq2*10^8 (69 puntos)

Ejemplo de Entrada

2

Ejemplo de Salida

3

Comments


  • 2
    linkyless  commented on Feb. 1, 2024, 9:13 a.m.

    ¿Alguna pista o patrón que me ayude a hacer este ejercicio?


    • 2
      karellgz  commented on Feb. 2, 2024, 12:54 a.m.

      X2.

      Yo logré sacar todos los lotes de prueba menos el último con esta heurística:

      • Basándome en esto:
      • Sea n un número cualquiera y cuyo totiente es igual a K (es decir, \varphi(n)=k) , y p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot...\cdot p_r^{\alpha_r} su factorización en primos entonces:
      • \varphi(n)=\varphi(p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot...\cdot p_r^{\alpha_r}), como la función totiente es multiplicativa en este caso: ...=\varphi(p_1^{\alpha_1})\cdot\varphi(p_2^{\alpha_2})\cdot...\cdot \varphi(p_r^{\alpha _r})
      • De ahí se llega a qué: k=p_1^{\alpha_1-1}(p_1-1)\cdot p_2^{\alpha_2-1}(p_2-1)\cdot...
      • Solo quedaría hacer fuerza bruta ahí poniendo primos a lo loco, y contar las soluciones que encuentres, claro que solo los primos cumplan que: p-1 | k
      • Quizás utilizar memorización si utilizas una solución recursiva (como yio)
      • También se puede observar que para cualquier K>1 impar, no hay solución

      Enlaces o cosas útiles:

      • Euler's Totient (en wikipedia en ingles, también está en espanyol)
      • Euler's Totient Function (Competitive programming Handbook, pg:201)

      Recomendado buscar:

      • Valencia o multiplicidad de un totiente

      Hope it helps!


  • -2
    Reynier  commented on April 1, 2023, 3:00 p.m.

    e?