Coprime Subsequences
Submit solution
Points:
100
Time limit:
2.0s
Memory limit:
256M
Author:
Problem types
Allowed languages
Ada, Assembly, Awk, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Perl, Prolog, Python, Scala, Swift, VB
Let's call a non-empty sequence of positive integers coprime if the greatest common divisor of all elements of this sequence is equal to .
Given an array a consisting of positive integers, find the number of its coprime subsequences. Since the answer may be very large, print it modulo .
Note that two subsequences are considered different if chosen indices are different. For example, in the array there are 3 different subsequences: (index 1), (index 2), and (indexes 1 and 2).
Input Specification
The first line contains one integer number ,
The second line contains integer numbers , .
Output Specification
Print the number of coprime subsequences of modulo .
Sample input
3
1 2 3
Sample output
5
Comments
Se añadió una segunda solución (con una idea diferente) a la editorial.
Se añadió una editorial.
Buenas, he estado intentado este exx y mi solucion debe dar AC de acuerdo a las restricciones del problema , pero me acabo de dar cuenta q en el caso 13 hay tres elementos en la entrada q son 0 , cuando te afirman q los elementos de entrada varian estre 1 <= ai <= 100000 , por favor en donde es q esta el defecto en el enunciado o el caso de Prueba? Saludos
Arreglado :)