Number Theory too.

Points: 100 (partial)

Time limit: 1.0s

Memory limit: 1G

Author:

FrankHG

Problem type

Allowed languages

C, C++, Java, Pascal, Python, VB

Definamos la función $\phi(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$ ~i~ $(1 \leq i \leq N)$ ~(1 \leq i \leq N)~ coprimos con $N$ ~N~. Dado un entero $K$ ~K~ diga la cantidad de números enteros positivos $N$ ~N~ que existen tales que $\phi(N)=K$ ~\phi(N)=K~.

Restricciones

$1 \leq K \leq 2*10^8$ ~1 \leq K \leq 2*10^8~

Entrada

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

Salida

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

Subtareas

$Subtarea$ ~Subtarea~ $1:$ ~1:~ $K$ ~K~ $es$ ~es~ $impar$ ~impar~ ( $1$ ~1~ punto)
$Subtarea$ ~Subtarea~ $2:$ ~2:~ $K$ ~K~ $\leq$ ~\leq~ $5*10^3$ ~5*10^3~ ( $2$ ~2~ puntos)
$Subtarea$ ~Subtarea~ $3:$ ~3:~ $K$ ~K~ $\leq$ ~\leq~ $2*10^5$ ~2*10^5~ ( $4$ ~4~ puntos)
$Subtarea$ ~Subtarea~ $4:$ ~4:~ $K$ ~K~ $\leq$ ~\leq~ $10^6$ ~10^6~ ( $8$ ~8~ puntos)
$Subtarea$ ~Subtarea~ $5:$ ~5:~ $K$ ~K~ $\leq$ ~\leq~ $10^7$ ~10^7~ ( $16$ ~16~ puntos)
$Subtarea$ ~Subtarea~ $6:$ ~6:~ $K$ ~K~ $\leq$ ~\leq~ $2*10^8$ ~2*10^8~ ( $69$ ~69~ puntos)

Ejemplo de Entrada

Ejemplo de Salida

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$ ~n~ un número cualquiera y cuyo totiente es igual a $K$ ~K~ (es decir, $\varphi(n)=k$ ~\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$ ~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$ ~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?