[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

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 4889번: Seinfeld  (0) 2020.03.19
[BOJ] 3078번: MALCOLM  (0) 2020.02.28
[BOJ] 14862번: 최대공약수 기댓값  (4) 2020.02.28
[BOJ] 16409번: Coprime Integers  (0) 2020.02.25
[BOJ] 8291번: Coprime Numbers  (0) 2020.02.25
[BOJ] 12107번: 약수 지우기 게임 1  (0) 2020.02.18
[BOJ] 13318번: 위험한 해싱  (0) 2020.02.01
  Comments
  • Sait2000
    http://boj.kr/d0764c6b030e4a9e8212be8272656653
    모듈로 값에 const를 안 붙이신 게 큰 거 같네요
    • 헐 되게 놀랍네요ㄷㄷ 제가 sait님 코드도 봤었는데 보고나서도 조금 오리무중이었어서 혹시 sait님 코드는 어떤 점 때문에 빠른건지, 아니면 아예 로직이 다른건지 알려주실 수 있으신가요?
    • Sait2000
      전처리 빼고 sqrt(200000)TK인 거 같아요. 저 링크 코드 기준으로 78번 줄에서 b[j]/i나 (a[j]-1)/i의 값이 변하지 않는 구간을 한번에 처리하면 되요. 저 구간의 개수가 b[j]나 a[j] 각각에 대해서 2 sqrt(b[j])개 쯤이니까 총 구간 수는 최대 4 sqrt(200000) K가 나와요.
    • 아 맞네요.. 이해했습니다 감사합니다ㅎㅎ 코드 많이 보고 배울게요ㅎㅎ
댓글 쓰기