# CFR 428 D. Winter is here

Problem Description:
You are given an array A[] of N values. For each subset that has gcd greater than 1, its contribution is gcd * size_of_subset. Output the sum of contributions for every such subset, modulo 1e9 + 7.

Constraints:
1 ≤ N ≤ 2e5
1 ≤ A[i] ≤ 1e6

Solution:
First use inclusion-exclusion technique to find the number of values that are multiple of i, denote as dp1[i].
Then for each i, find the sum of size of subset multiplied by the number of ways to select subset with gcd of multiple of i, denote as dp2[i].
Apply inclusion-exclusion to map dp2[i] with gcd exactly i, denote as dp3[i].
The answer is sum(dp3[i] * i for i in 1..MAXA).
Note that dp2[i] = sum(j * C(dp1[i], j) for j in 0..dp1[i]).
In order to compute this quickly, one can observe that: by differentiating this we get: and let x = 1: Code:

#include <bits/stdc++.h>

const int MOD = 1e9 + 7;

int inc_exc(int n, const std::vector<int> &a) {
int maxa = *std::max_element(a.begin(), a.end());
std::vector<int> dp(maxa + 1);
for (int v : a) ++dp[v];
for (int i = 1; i <= maxa; ++i) {
for (int j = i + i; j <= maxa; j += i) {
(dp[i] += dp[j]) %= MOD;
}
for (int p = dp[i] - 1, v = 2; p > 0; p >>= 1, v = 1LL * v * v % MOD) {
if (p & 1) {
dp[i] = 1LL * dp[i] * v % MOD;
}
}
}
int res = 0;
for (int i = maxa; i >= 2; --i) {
for (int j = i + i; j <= maxa; j += i) {
(dp[i] -= dp[j]) %= MOD;
}
(res += 1LL * i * dp[i] % MOD) %= MOD;
}
return (res + MOD) % MOD;
}

signed main() {
std::ios::sync_with_stdio(false);
int N;
std::cin >> N;
std::vector<int> A(N);
for (int i = 0; i < N; ++i) {
std::cin >> A[i];
}
std::cout << inc_exc(N, A) << std::endl;
return 0;
}