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:
${(1+x)^n = \sum_{k=0}^n x^k{n \choose k}}$
by differentiating this we get:
${n(1 + x)^{n - 1} = \sum_{k = 0}^n kx^{k - 1}{n \choose k} }$
and let x = 1:
${n2^{n - 1} = \sum_{k = 0}^n k{n \choose k} }$

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;
}