어떤 수 N의 진짜약수가 n개 존재하고, 그것을 오름차순으로 나열했을때 각각 p1, p2, ..., pn 이라고 해봅시다.
이때, p1 * pn = p2 * p(n-1) = p3 * p(n-2) = ... = p(i) * p(n+1-i) = N이 성립하며 n은 1 또는 짝수입니다. (n = 1일때는 p1 * p1 = N이 성립하므로 질문자님의 알고리즘은 정확합니다.)
n이 짝수일때, sum = N^(n/2) 이며, 우리가 찾는 수 N = (N^(n/2))^(2/n) = N^1 로 질문자님의 알고리즘에는 문제가 없어보입니다.
혹시 제 가정에서 틀린부분이 있다면 그 부분이 알고리즘에서 놓친 부분이 될 것 같습니다.
durid 3년 전
제가 생각했던 알고리즘은 이렇습니다.
1. arr[51]을 설정해주고 거기에 진짜약수를 모두 입력받음.
2. 진짜 약수를 모두 곱해서 sum이라고 하면, sum^(2/약수의 개수)= 우리가 찾는 수
(예제 기준으로, 4와 2가 진짜 약수라면 8^(2/2)).
구글링을 통해 정답으로 처리된 소스 코드를 구해서 입력값을 똑같이 넣어봤는데, 제가 생각할수 있는 범위까지는 출력이 전부 제 코드와 똑같이 나오더라고요.
혹시 제가 생각 못한 사이드케이스를 못 잡은건지 아니면 알고리즘 자체가 일정 구간에서만 성립하는 알고리즘인건지 질문드립니다.