choongmin   2년 전

단순하게 ∑μ(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인 경우는 미리 계산된 값을 이용하면 바로 구할 수 있는데, 일반적인 경우에는 어떻게 해야 답을 빨리 구할지 모르겠습니다. 혼자 힘으로 푸는 건 포기했으니 작은 힌트 주시면 감사하겠습니다.

pichulia   2년 전

[n/1] + [n/2] + [n/3] + ... + [n/k] (k<=n) 을 구하는 데 필요한 시간복잡도는

O(k) 으로 구하는 방법도 있고

O(sqrt(n)) 으로 구하는 방법도 있습니다.

힌트는 여기까지..

아 근데 너무 많이 알려준거같기도...

choongmin   2년 전

저는 저 식을 더 빨리 계산할 생각은 못하고 그림 그려가면서 완전 삽질했는데 얻은 거라곤 F(a, 2a) = F(a, a) + [F(2a, 2a) / 4] + 1 라는 사실뿐이었죠. 덕분에 풀었습니다. 감사합니다. 

adream   2년 전

삽질中...

댓글을 작성하려면 로그인해야 합니다.