ckdgus2482   5달 전

답이 자꾸 틀려서 그러는데 알고리즘 점검좀 부탁드리겠습니다.

최대공약수를 a 최소공배수를 b라고 했을때 p = ax, q=ay, b=axy로 놓고 계산했습니다. 답이 존재하려면 b/a가 자연수여야하므로 b/a를 int형 타입인 c로 치환했고요.

답이 여러개일때는 합이 최소인 p, q 쌍을 찾으라고 했으므로 xy가 c로 정해졌을때 a(x+y)가 최소인 정수 x, y 쌍을 찾는 문제가 됩니다.

a는 어차피 자연수이므로 a(x+y)가 최소인 x, y쌍은 x+y가 최소인 x, y쌍과 같겠죠.

그래서 x+y = k로 놓고 xy=c 방정식과 x+y=k 방정식의 연립방정식 해를 구했습니다.

근의 공식에 따라 (k-sqrt(k^2-4c))/2와 (k+sqrt(k^2-4c))/2가 나오는데 k는 x+y니까 정수여야하고 k가 정수라면 sqrt(k^2-4c) 또한 정수가 되어야만 합니다.

그래서 sqrt(k^2-4c)를 i로 놓고 i를 0부터 1씩 증가시키면서 k가 정수인 케이스를 찾았습니다. 0인 때는 중근으로 x랑 y랑 같은 상황일테고요.

이 때의 두 근이 각각 x와 y이므로 여기에 a를 곱해서 출력하게 했습니다.  만약 i가 짝수였다면 k^2 = 4c+i^2이므로 k^2도 짝수가 될 것이고 k^2이 짝수라는 얘기는 k 또한 짝수라는 얘기입니다. 홀수였다면 k^2도 홀수, k도 홀수가 되고요. 그래서 k-i와 k+i는 항상 2의 배수가 되므로 2로 나누면서 슬라이싱이 발생하는 케이스는 존재할 수 없을겁니다.

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