[n/1] + [n/2] + [n/3] + ... + [n/k] (k<=n) 을 구하는 데 필요한 시간복잡도는
O(k) 으로 구하는 방법도 있고
O(sqrt(n)) 으로 구하는 방법도 있습니다.
힌트는 여기까지..
아 근데 너무 많이 알려준거같기도...
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호
choongmin 9년 전
단순하게 ∑μ(k)(a/d/k)(b/d/k) (k = square-free and k <= min(a/d, b/d)) 식으로 하니 n=a=b=50000, d=1 인 경우 무려 10초가 넘게 걸리네요. a=b, a=2b, 2a=b인 경우는 미리 계산된 값을 이용하면 바로 구할 수 있는데, 일반적인 경우에는 어떻게 해야 답을 빨리 구할지 모르겠습니다. 혼자 힘으로 푸는 건 포기했으니 작은 힌트 주시면 감사하겠습니다.