Solución 1

Resolvamos un problema más general: Dados una secuencia ~a_1, a_2, \dots, a_n~ de enteros positivos y un entero positivo ~k~, calcular cuántas subsecuencias hay tal que el gcd de todos sus elementos sea ~k~, (llamemos a esta cantidad ~f(k)~). La respuesta al problema original sería cuando ~k = 1~, (es decir, ~f(1))~.

Observaciones:

• Si el gcd de una subsecuencia es ~k~, entonces todos los elementos de la subsecuencia deben ser múltiplos de ~k~.
• El conjunto de elementos múltiplos de ~k~ tiene como subsecuencias a:
  • Las subsecuencias cuyo gcd es ~k~.
  • Las subsecuencias cuyo gcd es ~2k~.
  • Las subsecuencias cuyo gcd es ~3k~.
  • Las subsecuencias cuyo gcd es ~4k~.
  • ...

Por tanto, ~f(k) + f(2k) + f(3k) + \dots = ~ [Cantidad de subsecuencias consistentes solamente de múltiplos de ~k~].

Obviamente, la cantidad de subsecuencias consistentes solamente de múltiplos de ~k~ es igual a ~2^{\text{Cantidad de múltiplos de k en el arreglo}} - 1~.

Por tanto, si ~cnt(k)~ es el número de múltiplos de ~k~ en el arreglo, entonces ~f(k) + f(2k) + f(3k) + \dots = 2^{cnt(k)} - 1~, lo que quiere decir que:

$$\displaystyle f(k) = 2^{cnt(k)} - 1 - f(2k) - f(3k) - f(4k) - \dots $$

No vamos iterar por todos los múltiplos de ~k~ hasta el infinito. Solo tenemos que iterar por los múltiplos de ~k~ menores o iguales que el máximo valor del arreglo. Llamemos ~M~ al máximo valor del arreglo.

Entonces, iteramos por ~k~ de manera decreciente desde ~M~ hasta ~1~; y para cada ~k~, usamos la recurrencia de arriba para computar ~f(k)~ en tiempo ~\mathcal{O}\left(\left\lfloor\frac{M}{k}\right\rfloor\right)~.

La complejidad temporal para calcular ~f()~ sería ~ \mathcal{O}\left(\displaystyle \sum_{k = 1}^{M} \left\lfloor\frac{M}{k}\right\rfloor\right) = \mathcal{O}(M\cdot \log M)~. Notemos que en el código mostrado abajo calculamos los divisores de ~x~ iterando hasta ~\sqrt{x}~, por lo cual esa parte toma en total tiempo ~\mathcal{O}(N\cdot \sqrt M)~.

Para otras formas de calcular cnt[] véase este artículo.

Código de ejemplo:

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll mod = (ll)1e9 + 7;
const int maxn = (int)2e5 + 5;

ll add(ll x, ll y){ return (x + y)%mod; }
ll rest(ll x, ll y){ return (x + mod - y)%mod; }

ll f[maxn]; // f[x]: cantidad de subsecuencias cuyo gcd es x
int cnt[maxn]; // cnt[x]: cantidad de múltiplos de x
ll ptwo[maxn]; // pwto[x]: 2 elevado a la x

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        ll x;
        cin >> x;
        for(int j = 1; j * j <= x; j++){
            if(x % j == 0){
                cnt[j]++;
                if(j * j != x)
                    cnt[x/j]++;
            }
        }
    }

    ptwo[0] = 1;
    for(int i = 1; i <= n; i++)
        ptwo[i] = add(ptwo[i-1], ptwo[i-1]);

    for(int g = maxn - 1; g >= 1; g--){
        f[g] = rest(ptwo[cnt[g]], 1); //realmente aquí no es necesario usar rest(), ya que ninguna potencia de 2 es múltiplo de 1e9 + 7
        for(int t = 2*g; t < maxn; t+=g)
            f[g] = rest(f[g], f[t]);
    }

    cout << f[1];

    return 0;
}

Solución 2

En esta solución usaremos principio de inclusión exclusión. Definamos ~M~ como el mayor valor del arreglo. Sean ~P = \{p_1, p_2, p_3\dots\}~ la secuencia de todos los primos menores o iguales que ~M~, (o sea, ~P = \{2, 3, 5, 7, \dots\}~). Sea ~S_i~ el conjunto de subsecuencias de ~a[\ ]~ tales que todos sus números son múltiplos de ~p_i~, por ejemplo: ~S_2~ sería el conjunto de todas las subsecuencias que consisten solamente de números pares.

Entonces, lo que queremos hallar es la cardinalidad (cantidad de elementos) del complemento de la unión de los ~S_i~. Es decir, de todas las posibles subscuencias, quitaremos las que pertenecen a al menos uno de los conjuntos ~S_i~, y la cantidad de subsecuencias restantes es la respuesta. La solución sería:

$$\displaystyle 2^n - 1 - \left\vert \bigcup_{i} S_i\right\vert$$

Para calcular ~\left\vert\bigcup_{i} S_i\right\vert~, según el principio de inclusión exclusión, iteramos por todos los subconjuntos de ~\{S_1, S_2, \dots\}~ y añadimos (en caso de que el subconjunto actual tenga tamaño impar) o restamos (en caso de que tenga tamaño par) a la solución el tamaño de la intersección de los ~S_i~ del subconjunto actual. Digamos que el subconjunto actual es ~\{S_{i_1}, S_{i_2}, \dots, S_{i_k}\}~, entonces lo que debemos añadir a la respuesta es la cantidad de subsecuencias que consisten solamente de múltiplos de ~p_{i_1} \cdot p_{i_2} \cdot \dots \cdot p_{i_k}~, que es ~2^{cnt[p_{i_1} \cdot p_{i_2} \cdot \dots \cdot p_{i_k}]} - 1~.

Obviamente, no podemos hacer esto explícitamente ya que hay demasiados primos. Notemos que hay una biyección entre cada subconjunto ~\{S_{i_1}, S_{i_2}, \dots, S_{i_k}\}~ y los productos ~p_{i_1} \cdot p_{i_2} \cdot \dots \cdot p_{i_k}~. Entonces, la respuesta es:

$$\displaystyle \sum_{i = 1}^M \mu(i)\cdot (2^{cnt[i]} - 1)$$

Aquí, ~\mu(i)~ es la función de Moebius, que retorna 0 si ~i~ no es libre de cuadrados (si tiene un primo con exponente mayor que 1 en su factorización), -1 si ~i~ tiene una cantidad impar de factores primos, y 1 si tiene una cantidad par de factores primos. Para calcular la función de Moebius, podemos usar el hecho de que es una función multiplicativa, y computar los primos con una criba.

La complejidad de esta solución depende de la criba y de qué tan rápido computamos ~cnt[\ ]~ (referirse a este artículo). Se puede lograr complejidad ~\mathcal{O}(M\log\log M)~.

Código de ejemplo:

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int maxn = (int)2e5 + 5;
const ll mod = (int)1e9 + 7; // 998244353

ll add(ll x, ll y){
    return (x + y)%mod;
}
ll rest(ll x, ll y){
    return add(x, mod - y);
}
ll mul(ll x, ll y){
    return x * y % mod;
}

int cnt[maxn], p[maxn], mu[maxn];
ll ptwo[maxn];

void sieve(){

    for(int i = 2; i < maxn; i+=2) p[i] = 2;

    for(int i = 3; i < maxn; i+=2) p[i] = i;

    for(int i = 3; i * i < maxn; i+=2)
        if(p[i] == i)
            for(int j = i*i; j < maxn; j+=2*i)
                p[j] = i;

    mu[1] = 1;
    for(int i = 2; i < maxn; i++){
        int j = i, k = 0;
        while(j % p[i] == 0)
            j /= p[i], k++;

        if(j == 1)
            mu[i] = rest(k == 0, k == 1);

        else
            mu[i] = mul(mu[j], mu[i/j]);
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    int n;
    cin >> n;
    ptwo[0] = 1;
    for(int i = 1; i <= n; i++){
        ll x; cin >> x;
        for(int j = 1; j * j <= x; j++){
            if(x % j == 0){
                cnt[j]++;
                if(j * j != x)
                    cnt[x/j]++;
            }
        }
        ptwo[i] = mul(ptwo[i-1], 2); 
    }

    sieve();

    ll ans = 0;

    for(int t = 1; t < maxn; t++)
        ans = add(ans, mul(mu[t], rest(ptwo[cnt[t]], 1)));

    cout << ans;

    return 0;
}