블로그 옮겼습니다

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

Algorithm/Problem Solving

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

sgc109 2017. 11. 19. 23:30

문제 링크


N <= 200000

100만 이하의 N개의 수로 이루어진 배열 D가 주어진다.

D의 모든 부분 집합 중 원소들의 gcd 가 1보다 큰 것들에 대해 

그 집합의 원소 수 * gcd 를 모두 더한 값을 구하는 문제이다.


cnt[i] : 입력으로 주어진 N개의 수들 중 i를 약수로 가지는 수들의 개수

c[i] : 집합에 포함된 원소들의 gcd 가 i인 모든 부분 집합들의 원소의 수의 합

이라고 정의내려보자.


그럼 우리는 모든 i에 대해 c[i] 를 구할 수만 있다면, 1보다 큰 모든 i 에 대해 i * c[i] 를 계산하여 모두 더하면 답이 될 것이다.

(왜냐면 원소들의 gcd 가 i 인 집합들에 대해 원소 수 * i 를 한다음 모두 더하면 결국 원소 소를 모두 더한뒤 i를 곱한 것과

같기 때문이다.)

그런데 c[i] 는 cnt[i] 와 포함 배제의 원리를 통해

\(O(N\sqrt{N})\) 에 계산할 수가 있다. (1중 포문 돌면서 각 수의 약수를 체크하며 돌기때문.)


우선 c[i] 를 cnt[i] 로 구하는 원리에 대해 알아보자.

원소의 개수가 n개인 어떤 집합 A의 모든 부분 집합들의 원소 수의 합은

\(n \times 2^{n-1}\) 인데, (이유는 아래 더보기를 누르시오)


어떠한 수들의 gcd가 i이려면, i를 약수로 갖지 않는 수가 하나 라도 껴있으면 안되기 때문에

우선 i를 약수로 가지는 입력으로 주어진 모든 수들을 원소로 가지는 집합 A를 만들어 보자.

그럼 주어진 입력들중 일부를 원소로 갖고 원소들의 gcd 가 i인 집합들은 모두 A의 부분 집합일 것이다.

그럼 A 의 모든 부분 집합들은 원소들의 gcd 가 i인 집합들과 원소들의 gcd가 i의 배수인 집합들로 이루어져 있을 것이다.

즉, 원소들의 gcd 가 i 인 모든 집합들을 원소로 갖는 집합을 S[i] 라고 해보자. 그럼

공집합이 아닌 A의 부분 집합들의 집합 = S[i] 와 S[j1], S[j2], ... 의 합집합이라고 볼 수 있다. (j1, j2, ... 는 i를 약수로 갖는 수)


S[i] 의 모든 원소(집합)들의 원소 수의 합이 바로 c[i] 이므로

c[i] = cnt[i] * (2^(cnt[i]-1)) - c[j1] - c[j2] - ... 이다.

그러면 어떤 i라는 수에 대해 c[i]를 구하는 시점에 이미 i의 모든 배수들 j에 대해 c[j] 가 c[i] 에서 빼져있어야한다.

왜냐하면 단순히 cnt[i] * (2^(cnt[i] - 1)) 를 하면 그 안에 집합에 포함된 원소들의 gcd 가 i가 아닌 i의 배수인 경우도

모두 포함되어 있기때문이다. 


그런데 입력으로 주어지는 수는 최대 100만인데 모든 i에 대해

모든 배수를 검사하면 하나의 i당 100만 / i 번 검사를 하게 되므로 시간이 너무

오래 걸리므로 반대로 i 의 배수인 j 를 먼저 계산하고 j의 모든 약수들에 대해

미리 빼놓는다면 될 것이다. 아니 애초에 굳이 이렇게 생각을 할 필요도 없이

아까 말했듯, i의 모든 배수 j에 대해 c[j] 를 빼려면 애초에 이미 c[j] 가 구해져

있어야 하므로 가장 큰 수 부터 1씩 감소시키며 차례대로 c[i] 를 계산하고 

i의 약수들에 대해 미리 c[i] 를 빼놓는 식으로 하면 될 것이고, 방금 말한

c[i] 를 계산한다는 것은, 이미 i 의 배수들 j에 대해 c[j] 가 모두 빼져있을것이므로

(큰 수부터 계산하고 약수들에 빼기 때문에) 그냥 cnt[i] * (2^(cnt[i]-1)) 를 더해주기만

하면 된다.

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
#include <bits/stdc++.h>
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
#define fastio() ios::sync_with_stdio(0),cin.tie(0);
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int inf = 0x3c3c3c3c;
const ll infl = 0x3c3c3c3c3c3c3c3c;
 
int N;
ll pow2[200003];
ll cnt[1000003];
ll c[1000003];
int main(){
    fastio();
    pow2[0= 1;
    for(int i = 1; i < 200003; i++) pow2[i] = (pow2[i - 1* 2) % mod;
    cin >> N;
    for(int i = 0; i < N; i++){
        int a;
        cin >> a;
        for(int j = 1; j * j <= a; j++){
            if(a % j) continue;
            cnt[j]++;
            if(j * j != a) cnt[a / j]++;
        }
    }
    for(int i = 1000000; i >= 2; i--){
        if(!cnt[i]) continue;
        c[i] = (c[i] + cnt[i] * pow2[cnt[i] - 1]) % mod;
        for(int j = 2; j * j <= i; j++){
            if(i % j) continue;
            c[j] = (c[j] - c[i] + mod) % mod;
            if(j * j != i) c[i / j] = (c[i / j] - c[i] + mod) % mod;
        }
    }
    ll ans = 0;
    for(int i = 2; i <= 1000000; i++) ans = (ans + i * c[i]) % mod;
    cout << ans;
}
 
cs


Comments