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

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

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

Input Specification

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

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

Output Specification

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

Sample input

 3
 1 2 3

Sample output

 5

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 :)