6개의 댓글이 있습니다.
-
-
TurtleShip -
좋은 설명 감사드립니다. 혹시 소수 구하는 부분에서 setbit과 getbit에 대해서 부연 설명 가능하신가요?
12년 전 link
-
-
-
TurtleShip -
astein님, astein님의 코드를 썼을 경우
N = 6140400029153458
M = 6140401
에서 Floating point exception: 8 이라는 에러가 나요.디버깅 해보니, numDivisor(n)에서,
maxi = 78360704 인데, 이 값은
소수를 넣어놓은 배열 p의 크기 51000000 보다 커서 메모리 참조값이 어긋나서 에러가 나오는 거 같아요. 2가지를 알고 싶어요.
1. 왜 배열 p의 크기를 51000000 로 하셨나요?
2. large data 테스트 할 때 위의 에러가 발생 하셨을 것 같은데 어떻게 해결하셨나요?
12년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
astein
저도 풀었습니다!
기본 알고리즘은 아래 Andromeda님이 써 주신 내용과 비슷하고요.
Large Data 1000개 전부 구하는데 30초정도 걸리네요.
속도를 개선하는 요소는 크게 두 가지입니다.
1) [A, B] 구간의 소수를 빨리 구한다.
2) N 이하의 수 중에서 약수가 nd개인 경우가 있다.
시간만 무한하다면야 모든 경우를 세는것이 제일 확실한 방법이지만, 우리에게는 8분의 여유밖에 없습니다. 따라서 답이 될 수 없는 경우는 탐색을 하지 않는 것이 필요하지요.
D번 문제에서 큰 데이터를 테스트 하신 분들은 nd = 8 또는 16일 때 프로그램의 실행속도가 매우 느려지는 현상이 발생할 것입니다. N = 1억 정도이고 m = 2인 입력이 들어왔다면 소수 3개의 곱이 1억이 되지 않는 경우는 아주 많기 때문이지요. 위의 1)을 통해서 많이 개선이 되긴 하지만 여전히 느린것은 마찬가지입니다.
답이 p1 * p2 * p3 (단 p1 < p2 < p3) 인 경우, p1에 2부터 차례대로 소수를 넣고 테스트하게 되는데, 여기에서 답이 존재하는 최대 p1이 몇인지 바로 판단할 수만 있다면 많은 시간을 아낄 수 있을 것입니다. p1 = 2나 3일 경우에는 답이 존재하겠지만 1000을 넘는 소수라면 p2, p3를 아무리 골라도 세 수의 곱은 1억을 넘게 될 테니까요.
즉 p1 ^ 3 > N을 만족하는 p1은 그 다음수를 어떻게 고르더라도 해가 될 수 없다는 것을 알 수 있습니다. (물론 p1 ^ 3 <= N 을 만족한다고 해서 p1에 항상 답을 가진다는 보장은 없습니다.)
nd = 8일때는 세제곱으로 테스트로 충분한 이유는 a^7, a^3 * b, a * b * c의 세 가지 형태 중에서 모든 소수에 a를 대입했을 때 세제곱이 나오기 때문이지요. 비슷한 예로 nd = 12일 때에는 a^11, a^5 * b, a^3 * b^2, a^2 * b * c가 있고, 이는 네제곱으로 테스트를 해서 a의 상한을 정할 수 있습니다.
소스코드에서 minmul 배열은 nd가 주어졌을 때 몇제곱이 상한인지를 계산하고 있습니다. 그리고 실제로 k제곱 하게 되면 수행시간이 오래 걸리게 되므로 x ^ k <= n을 비교하는 대신 x <= n ^ (1 / k)를 비교합니다. 이렇게 하면 n과 k는 고정이기 때문에 매번 제곱연산을 할 필요가 없게 되지요.
조만간 C번도 풀어보겠습니다.
12년 전