题目分析

显然我们不可能直接计算每一个子序列的贡献，而应该计算对于每一个gcd对答案的贡献。

考虑容斥。按照套路：

设(q(i))表示序列(gcd)为(i)的倍数的序列长度和。

设(g(i))表示序列(gcd)为(i)的序列对答案的贡献。

设(f(i))表示序列(gcd)为(i)的序列的容斥系数。

对于(q(i))，显然我们可以利用调和级数在(O(nlogn))的时间复杂度下求出(gcd)为(i)的数的个数。
那么它们形成的子序列的长度和为：(sumlimits_{i=0}^ni*dbinom{n}{i}=n* 2^{n-1})

对于(g(i))，本题中显然(g(i)=i)。

对于(f(i))，我们按照套路可以得到：(g(x)=sumlimits_{d|x}f(d))
这个十分显然的可以直接上莫比乌斯反演。于是得到: (f(x)=sumlimits_{d|x}mu(frac{x}{d})g(d))
这个也很容易利用调和级数在(O(nlogn))的时间复杂度下计算出来。

于是最终答案即为：(sumlimits_{i=2}^{10^6}q(i)* f(i))