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