[BOJ] 14862번: 최대공약수 기댓값

https://www.acmicpc.net/problem/14862

 

맨 처음에는 prob1[i]를 gcd가 i의 배수일 확률($PQ^{-1}$), prob2[i]를 gcd가 i일 확률로 두고 $O(200000lg200000TK)$로 구했으나 시간초과가 발생했습니다.

 

그래서 mobius function을 통해 각 prob1[i]에 얼마가 곱해져야 하는지를 전처리로 계산해서 $O(200000lg200000 + 200000TK)$로 코드를 짜서 아주 간신히 통과됐습니다. 일단 $200000TK$가 왜 1.9초 가까이 걸리는지도 조금 의아하고, 수행시간이 아주 빠른 분들 코드를 봤는데 보고 나서도 오리무중이네요.

 

https://github.com/blisstoner/BOJ/blob/master/14862.cpp