[Codeforces] 839D. Winter is here

題目連結:http://codeforces.com/problemset/problem/839/D

---

超級無敵久沒寫blog了，記錄一下這題好了，我過然數學還是不太好QQ
首先我們可能會想要對每個gcd都計算答案，那這時候我們可能會想知道有可能對這個gcd有貢獻的人會有誰，所以不妨先計算好有多少個數字含有因數$i$。那接著我們就直接計算總長度，對於每個因數$i$計算$\sum_{j=0}^{cnt[i]} j\cdot \binom{cnt[i]}{j}$但是這樣會重複計算到太多人，所以要扣掉他的2倍、3倍....的答案，而要算答案的時候則再乘上$i$即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int N = 200000 + 5;
const int C = 1000000 + 5;
const int MOD = 1000000007;

int arr[N], cnt[C];
lld ans[C], two[N];

int main(int argc, char* argv[]){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n; cin>>n;
	two[0] = 1;
	for(int i=1;i<n;i++) two[i] = two[i-1]*2 % MOD;
	for(int i=0;i<n;i++){
		cin>>arr[i];
		cnt[arr[i]]++;
	}
	for(int i=1;i<=C;i++) for(int j=2;j*i<=C;j++){
		cnt[i] += cnt[i*j];
	}
	lld ret = 0;
	for(int i=C;i>=2;i--){
		if(cnt[i]==0) continue;
		ans[i] = cnt[i] * two[cnt[i]-1] % MOD;
		for(int j=2;j*i<=C;j++) ans[i] = (ans[i]-ans[j*i]+MOD)%MOD;
		ret = (ret + i*ans[i]%MOD) % MOD;
	}
	cout << ret << '\n';
	return 0;
}