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

http://codeforces.com/contest/839/problem/D

---

문제 요약

원소의 개수가 $N$인 배열이 있다. 우리는 다음 조건을 만족하는 부분 배열(subsequence 개념)을 찾을 것이다.

• $N$개의 원소중 $k$개를 고른다.
• 그 $k$개의 원소의 최대공약수가 1보다 크다.

이러한 부분 배열이 있을 때, 이 배열의 값을 $k\times gcd(a_1,a_2,...,a_k)$ 이라 한다. 이 때 가능한 모든 부분 배열의 값을 더해 1e9+7로 나눈 값을 구하는 문제이다.

---

풀이

우리는 2개의 배열이 필요하다. $cnt[i]$와 $ans[i]$. 우선 $cnt[i]$를 모든 원소 $a_j$에 대해 $i$로 나누어 떨어지는 $a_j$의 개수라 하자. 그러니까 모든 $a_j$의 약수에 대해 cnt값을 1씩 증가시켜준다고 생각하면 된다. 그 다음 $cnt[i]=c$라 했을 때, $ans[i]$는 $\sum _{ k=1 }^{ c }{ k }\binom{c}{k}$ 값이다. $k$를 곱하는 건 문제에서 요구하는 바이고, $\binom{c}{k}$ 은 $c$개 중에서 $k$개를 고르는 경우의 수이다. 이 식을 변형해보자.

위 식을 통해 $ans[i]=cnt[i]\times 2^{cnt[i]-1}$ 임을 알 수 있다.

하지만 여기서 끝이 아니다.

$ans[2]$중에서는 $ans[4]$에 포함된 것도 있을테고 $ans[6]$에 포함된 것도 있을 것이다. 이러한 것들을 다 제거해줘야한다. 

따라서 다음과 같은 과정을 거쳐야 진짜배기 $ans[i]$를 구할 수 있다.

$ans[i] = ans[i] - ans[2*i] - ans[3*i] .... $

이러면 $ans[i]$에는 최대공약수가 $i$인 부분 배열들에 대한 정보만 남는다.

최종적으로 답은 $\sum _{ i=2 }^{ 1000000 }{ i\times ans[i]}$라는 것은 굳이 이유를 설명하지 않아도 알 수 있을 것이다. 

$T$를 $a_i$의 최대값 이라 할 때 시간복잡도는 $O(T+T/2+T/3+...) = O(TlgT)$가 된다. 시간복잡도가 이렇게 되는 이유는 이 링크에서 확인하도록.