pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces Round #428 (Div. 2): D. Winter is here

http://codeforces.com/problemset/problem/839/D

dp[i]:=gcdがiになるような部分列の総数とすると以下の関係式が成り立つ。

\begin{equation}
dp[i]=\text{gcdがiの倍数の部分列の総数}-dp[2i]-dp[3i]-dp[4i]-\cdots
\end{equation}

gcdがiの倍数になる部分列の総数を得るために、\( \sum_{k=1}^{n} k\binom{n}{k} \) を計算する必要が出てくるが、\((1+x)^n\) を微分すれば分かる。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

constexpr int MOD = 1e9 + 7;

struct modint {
  int n;
  modint(int n = 0) : n(n) {}
};

modint operator+(modint a, modint b) { return modint((a.n += b.n) >= MOD ? a.n - MOD : a.n); }
modint operator-(modint a, modint b) { return modint((a.n -= b.n) < 0 ? a.n + MOD : a.n); }
modint operator*(modint a, modint b) { return modint(1LL * a.n * b.n % MOD); }
modint &operator+=(modint &a, modint b) { return a = a + b; }
modint &operator-=(modint &a, modint b) { return a = a - b; }
modint &operator*=(modint &a, modint b) { return a = a * b; }

template<typename T>
modint modpow(modint a, T b) {
  modint ret = 1;
  for (; b > 0; b >>= 1, a *= a) if (b & 1) ret *= a;
  return ret;
}

int main() {
  constexpr int N = 1.01e6;
  int n;
  cin >> n;
  vector<modint> dp(N);
  for (int i = 0; i < n; i++) {
    int a;
    scanf("%d", &a);
    dp[a] += 1;
  }
  for (int i = 1; i < N; i++) {
    for (int j = i * 2; j < N; j += i) dp[i] += dp[j];
    dp[i] *= modpow(2, dp[i].n - 1);
  }
  modint ans = 0;
  for (int i = N - 1; i >= 2; i--) {
    for (int j = i * 2; j < N; j += i) dp[i] -= dp[j];
    ans += i * dp[i];
  }
  cout << ans.n << endl;
}