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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#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;
}
------ 本文结束 ------