求$gcd>1$的所有$gcd(a_i,a_{i+1}…a_{n})*(n-i+1)$的和

首先先标记所有出现的数。从高到低枚举一个数k，记录它的倍数出现次数cnt，那么当前所有组合的答案就是$ans[k]=cnt*2^{cnt-1}$，但是这个答案只有gcd=k的组合是没被计算过的，其他已经被k的倍数计算过了，所以要减去此前算过的所有n的$ans[k|n]$。

/** @Date    : 2017-08-13 14:38:39

  * @FileName: 839D 容斥.cpp

  * @Platform: Windows

  * @Author  : Lweleth (SoungEarlf@gmail.com)

  * @Link    : https://github.com/

  * @Version : $Id$

  */

#include <bits/stdc++.h>

#define LL long long

#define PII pair<int ,int>

#define MP(x, y) make_pair((x),(y))

#define fi first

#define se second

#define PB(x) push_back((x))

#define MMG(x) memset((x), -1,sizeof(x))

#define MMF(x) memset((x),0,sizeof(x))

#define MMI(x) memset((x), INF, sizeof(x))

using namespace std;

const int INF = 0x3f3f3f3f;

const int N = 1e6+20;

const double eps = 1e-8;

const LL mod = 1e9 + 7;

LL fpow(LL x, LL n)

{

	LL ans = 1;

	while(n > 0)

	{

		if(n & 1)

			ans = (ans * x % mod + mod) % mod;

		x = (x * x % mod + mod)% mod;

		n >>= 1;

	}

	return ans;

}

LL cnt[N];

LL rep[N];

int n;

int main()

{

	while(cin >> n)

	{

		MMF(cnt);

		MMF(rep);

		int x;

		for(int i = 0; i < n; i++) scanf("%d", &x), cnt[x]++;

		LL ans = 0;

		for(int i = 1000000; i >= 2; i--)

		{

			LL c = 0;

			for(int j = i; j <= 1000000; j+=i)

				c += cnt[j];

			if(!c)

				continue;

			//cout << i << c << endl;

			rep[i] = (c * fpow(2, c - 1) % mod + mod) % mod;

			//cout << rep[i] << endl;

			for(int j = i + i; j <= 1000000; j+=i)

				if(rep[j])

					rep[i] = (rep[i] - rep[j] + mod) % mod;

			//cout << rep[i] << endl;

			ans = (ans + rep[i] * (LL)i % mod + mod) % mod;

		}

		printf("%lld\n", ans);

	}

    return 0;

}