3560 - How Many Square Free Numbers 3560 - Cuántos Números Libres de Cuadrados 3560 - How Many Square Free Numbers

Statistics Sub: 339 | AC: 53 | AC%: 15,63 | Score: 2,74
Created by Frank Arteaga Salgado
Added by frankr (2016-03-19)
Limits
Total Time: 30000 MS | Test Time: 3000 MS |Memory: 256 MB | Output: 64 MB | Size: 9 KB
Enabled languages
Available in

Description

One day Renicom invited his friends home to solve competitive programming challenges. While searching on Google, they discovered The Online Encyclopedia of Integer Sequences (OEIS), which excited them very much, because they're fans to the integer numbers properties. 



After solving the problems, each of them, included Renicom, wrote a square free number on his notebook and went to his house. A number X is square free if for every prime p that divides X, then p^2 does not divide X. Between the house of Renicom and each of the houses of his friends there is a direct path.

Another day, Renicom picked up his notebook and went to visit his friends. Every time he pass for the house of a friend (he can visit a friend more than once in the same day) he multiplies the square free number written by his friend by the result of the multiplication of the previous house or by his square free number if this is the first house. You can assume that Renicom visits at least one of his friends when goes out from home.

At the end of the day, when Renicom comes back to his house, he can have a multiplication that is a square free number or not, so he wants to know how many distinct square free numbers can be generated as the final result of a sequence of visits to his friends.
Un día Renicom invitó a su casa a sus amigos para resolver retos de programación competitva, durante la búsqueda en Google descubrieron The Online Encyclopedia of Integer Sequence (OEIS) lo cual los entusiasmó mucho puesto que son fans a las propiedades de los números enteros. 



Después de resolver los problemas, cada uno de ellos, incluido Renicom, apuntó un número libre de cuadrados en su libreta de notas y se marchó a su casa. Un número X es libre de cuadrados si para todo primo p que divida a X entonces p^2 no divide a X. Entre cada par de casas de Renicom y sus amigos hay un camino directo.

Otro día Renicom coge su libreta de entrenamiento y sale visitar a sus amigos, además cada vez que pasa por la casa de un amigo (en el día puede visitar a un amigo más de una vez) él multiplica el número libre de cuadrados apuntado por su amigo la vez pasada por el resultado de la multiplicación echa en la casa previa o por su número libre de cuadrados si es el primer amigo en visitar. Asuma que Renicom cuando sale de su casa visita a al menos uno de sus amigos.

Al final del día cuando Renicom regresa a su casa puede tener una multiplicación que sea un número libre de cuadrados o no, él quiere saber cuántos números libres de cuadrados distintos pueden generarse en el resultado final de una secuencia de visitas a sus amigos.
One day Renicom invited his friends home to solve competitive programming challenges. While searching on Google, they discovered The Online Encyclopedia of Integer Sequences (OEIS), which excited them very much, because they're fans to the integer numbers properties. 



After solving the problems, each of them, included Renicom, wrote a square free number on his notebook and went to his house. A number X is square free if for every prime p that divides X, then p^2 does not divide X. Between the house of Renicom and each of the houses of his friends there is a direct path.

Another day, Renicom picked up his notebook and went to visit his friends. Every time he pass for the house of a friend (he can visit a friend more than once in the same day) he multiplies the square free number written by his friend by the result of the multiplication of the previous house or by his square free number if this is the first house. You can assume that Renicom visits at least one of his friends when goes out from home.

At the end of the day, when Renicom comes back to his house, he can have a multiplication that is a square free number or not, so he wants to know how many distinct square free numbers can be generated as the final result of a sequence of visits to his friends.

Input specification

On the first line will appear N (1 <= N <= 20) which is the amount of friends of Renicom. Then, on the second line, there will be N+1 positive integers, each of them is a square free number. The first is the number written by Renicom and the next N the ones of his friends. Each number is less than 10^16.
En la primera línea aparecerá N (1 <= N <= 20) que es la cantidad de amigos de Renicom, luego en la segunda línea aparecerán N + 1 enteros positivos, todos ellos libres de cuadrados, el primero es el apuntado por Renicom y los N siguientes los de sus amigos. Cada número es menor que 10^16.
On the first line will appear N (1 <= N <= 20) which is the amount of friends of Renicom. Then, on the second line, there will be N+1 positive integers, each of them is a square free number. The first is the number written by Renicom and the next N the ones of his friends. Each number is less than 10^16.

Output specification

Print just one integer, the amount of square free numbers that can be obtained as the final result of a sequence of visits of Renicom.
Imprima un solo entero que es la cantidad de números libres de cuadrados distintos que pueden obtenerse como resultado final de la secuencia de visitas de Renicom.
On the first line will appear N (1 <= N <= 20) which is the amount of friends of Renicom. Then, on the second line, there will be N+1 positive integers, each of them is a square free number. The first is the number written by Renicom and the next N the ones of his friends. Each number is less than 10^16.

Sample input

3
3 35 6 17

Sample output

3

Hint(s)

For the sample input the possible square free numbers are 51, 105 and 1785.
Para el ejemplo de entrada los números libres de cuadrados posibles son 51, 105 y 1785.
For the sample input the possible square free numbers are 51, 105 and 1785.

Recommendation

We have carefully selected several similar problems: 3378 | 3675 | 3377 | 2916 | 3515 | 1960