Seja X(k) o conjunto dos vetores de tamanaho N com menor elemento entre A e B, maior elemento entre C e D, e gcd = k.

Ou seja, a solucao do problema eh |X(1)|... entao nos temos:

Seja X a uniao de X(k) para todos os k (apesar de ser uma uniao de infinitos "k", X eh finito no final... nao tem mais que (D - A + 1)^N elementos)

|X(1)|  =  |X(1)| * mu(1)
        =  \sum_{k = 1, ..., infinity} |X(k)| * \sum_{d divisor de k} mu(d)

A segunda igualdade acontece por causa da definicao "2"... todos os termos com k >= 2 vao desaparecer da soma.

===== Inicio da parte 2 =====

Continuando as equacoes, nos temos:

|X(1)|  =  |X(1)| * mu(1)
        =  \sum_{k = 1, ..., infinity} |X(k)| * \sum_{d divisor de k} mu(d) # agora eu vou trocar a ordem dos somatorios
        =  \sum_{d = 1, ..., infinity} mu(d) \sum_{k multiple of d} |X(k)|
        =  \sum_{d = 1, ..., infinity} mu(d) f(d)

Onde: f(d) = \sum_{k multiple of d} |X(k)|

Vamos pensar um pouco em f(d)... em bom portugues:
f(d) = numero de sequencias com menor elemento entre A e B, e maior elemento entre C e D, tal que o gcd eh um multiplo de d.

Aqui vem o trigesimo oitavo pulo do gato: o gcd eh multiplo de d se e somente se todos os elementos sao multiplos de d.

Entao podemos reescrever f(d) como:

f(d) = numero de sequencias com menor entre A e B, maior entre C e D, tal que todos os elementos sao multiplos de d.