Codeforces 839D(组合数+容斥原理+二项式定理)

Codeforces 839D
考虑枚举$gcd$为$i$.
则每个$i​$贡献为$i \times \sum( j \times C^j_k)​$, $i​$为$gcd​$, $k​$为$a_i​$中有$i​$因子的数的个数
$\sum( j \times C^j_k) = \sum( j \times C^{j-1}_{k-1} \times k \div j)$
$=\sum(C^{j-1}_{k-1} \times k)$
$=k \times 2^{k-1}$
然后每个$i$贡献为$i \times k \times 2^{k-1}$
然后因为$i=y$会重复计算$i=2y,3y…ny$的情况，所以要容斥减一下
然后注意longlong，注意溢出，注意数组大小

Codeforces Submission

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const LL MO = 1000000007;
LL n, dp[1000000 + 5], bs[1000000 + 5], w[1000000 + 5];
void clean() {
    ms(w, 0);
}
void solve() {
    clean();
    for (LL i = bs[0] = 1; i <= n; i++) bs[i] = (bs[i - 1] * 2) % MO;
    LL mx = 0, ans = 0;
    for (LL x, i = 1; i <= n; i++) scanf("%I64d", &x), w[x]++, mx = max(mx, x);
    for (LL i = mx; i > 1; i--) {
        LL k = 0;
        for (int j = i; j <= mx; j += i) k = (k + w[j]) % MO;
        if (k == 0) continue;
        dp[i] = (bs[k - 1] * k) % MO;
        for (int j = i + i; j <= mx; j += i) dp[i] = (dp[i] - dp[j] + MO) % MO;
        ans = (dp[i] * i + ans) % MO;
    }
    printf("%I64d\n", ans);
}
int main() {
    scanf("%I64d", &n), solve();
    return 0;
}