문제
삼각수는 1, 2, 3, ...개의 점을 줄마다 늘려 삼각형을 만들 때 필요한 점의 개수입니다. T(1) = 1, T(2) = 3, T(3) = 6이고 T(k) = k(k + 1) / 2입니다. 삼각수를 차례로 살펴보다가 양의 약수가 d개 이상인 첫 번째 수에서 멈추세요(1과 자기 자신도 약수에 포함합니다).
highly_divisible_triangular(d) 함수를 구현하세요.
약수를 하나씩 세면 큰 입력에서는 너무 느립니다. 대신 소인수분해를 하세요. n = p^a × q^b × ...이면 약수의 개수는 (a + 1)(b + 1)...개입니다. k와 k + 1은 공통인 인수가 없으므로 따로따로 소인수분해할 수 있습니다.
입력
d: 필요한 약수의 개수입니다.
출력
약수가 d개 이상인 첫 번째 삼각수를 반환합니다.
제약 조건
1 ≤ d ≤ 300
예시
입력:
d = 4
예상 출력:
expected = 6
입력:
long long d = 4;
예상 출력:
long long expected = 6;
입력:
long d = 4;
예상 출력:
long expected = 6;
설명
1은 약수가 1개, 3은 2개이지만 6은 4개(1, 2, 3, 6)이므로 답은 6입니다.
입력:
d = 9
예상 출력:
expected = 36
입력:
long long d = 9;
예상 출력:
long long expected = 36;
입력:
long d = 9;
예상 출력:
long expected = 36;
설명
28은 약수가 6개이고 36 = 2² × 3²은 3 × 3 = 9개(1, 2, 3, 4, 6, 9, 12, 18, 36)이므로 답은 36입니다.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
T(k) = k(k + 1) / 2이고, k와 k + 1은 공통인수가 없습니다.
힌트 2
k와 k + 1 중 짝수인 쪽을 2로 나눈 다음, 각 부분의 약수 개수를 세세요.
힌트 3
서로소인 수들의 곱의 약수 개수는 각 약수 개수의 곱입니다.
예상 복잡도
시간 O(K √K) (K는 시도한 삼각수의 개수), 추가 공간 O(1)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.