Coprime Subsequences

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 $a_1, a_2, \dots, a_n$ ~a_1, a_2, \dots, a_n~ coprime if the greatest common divisor of all elements of this sequence is equal to $1$ ~1~.

Given an array a consisting of $n$ ~n~ positive integers, find the number of its coprime subsequences. Since the answer may be very large, print it modulo $10^9 + 7$ ~10^9 + 7~.

Note that two subsequences are considered different if chosen indices are different. For example, in the array $[1, 1]$ ~[1, 1]~ there are 3 different subsequences: $[1]$ ~[1]~ (index 1), $[1]$ ~[1]~ (index 2), and $[1, 1]$ ~[1, 1]~ (indexes 1 and 2).

Input Specification

The first line contains one integer number $n$ ~n~, $(1\le n \le 100000)$ ~(1\le n \le 100000)~

The second line contains $n$ ~n~ integer numbers $a_1, a_2, \dots, a_n$ ~a_1, a_2, \dots, a_n~, $(1 \le a_i \le 100000)$ ~(1 \le a_i \le 100000)~.

Output Specification

Print the number of coprime subsequences of $a$ ~a~ modulo $10^9 + 7$ ~10^9 + 7~.

Sample input

 3
 1 2 3

Sample output

Comments

0

aniervs commented on July 22, 2021, 1:20 p.m.

Se añadió una segunda solución (con una idea diferente) a la editorial.

2

aniervs commented on July 21, 2021, 7:45 p.m.

Se añadió una editorial.

0

hohemhein commented on July 21, 2021, 8:04 a.m.

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

1

aniervs commented on July 21, 2021, 3:53 p.m.

Arreglado :)