DDOSvoid's Blog

CF 839D Winter is here

发表于 更新于 分类于
本文字数： 1.4k 阅读时长 ≈ 1 分钟

题目描述

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

简要题意：给定一个长度为 $n$ 的序列 $a_i$，求所有子序列的价值的和，一个子序列如果长度为 $k$，且 $gcd$ 为 $d$，那么这个子序列的价值为 $k\times d$

$n\le 2\times 10^5,a_i\le 10^6$

Solution

令 $g_n$ 表示 $gcd$ 是 $n$ 的每个序列的价值，这里为了方便计算，我们把 $n$ 提出来

即最终答案为 $\sum_{i=2}^n ig_i$

我们考虑求 $f_n=\sum_{n|d}g_d$，这个东西我们可以直接枚举 $n$ 的倍数，算出有多少数是 $n$ 的倍数，不妨设有 $s$ 个，那么 $f_n=\sum_{i=1}^s i\binom{s}{i}=s2^{s-1}$，然后我们再反演回去求出 $g_n$ 即可

时间复杂度 $O(n\log n)$

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <cstdio>
#define maxn 1000010
#define ll long long
using namespace std;

const int p = 1000000007;

ll pow_mod(ll x, ll n) {
    ll s = 1;
    for (; n; n >>= 1) {
        if (n & 1) s = s * x % p;
        x = x * x % p;
    }
    return s; 
} 

int n, m, num[maxn];

int pri[maxn], c1, mu[maxn]; bool isp[maxn];
void init_isp(int n) {
    mu[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!isp[i]) pri[++c1] = i, mu[i] = -1; 
        for (int j = 1; j <= c1 && i * pri[j] <= n; ++j) {
            isp[i * pri[j]] = 1;
            if (i % pri[j] == 0) break;
            mu[i * pri[j]] = -mu[i]; 
        }
    }
} 

int f[maxn], g[maxn], ans; 
int main() {
    cin >> n; 
    for (int i = 1; i <= n; ++i) {
        int x; cin >> x;
        ++num[x]; m = max(m, x); 
    } init_isp(m);
    for (int i = 2; i <= m; ++i) {
        int s = 0; 
        for (int j = i; j <= m; j += i) s += num[j];
        if (s) f[i] = s * pow_mod(2, s - 1) % p;
    }
    for (int i = 2; i <= m; ++i)
        for (int j = i; j <= m; j += i) g[i] = (g[i] + f[j] * mu[j / i]) % p;
    for (int i = 2; i <= m; ++i) ans = (ans + (ll) i * g[i]) % p;
    cout << ans << "\n"; 
    return 0;
}