모든 챌린지
보통 0명 해결 정답률 0%

약수가 많은 삼각수

약수가 d개 이상인 첫 번째 삼각수를 구합니다.

배우게 될 내용

  • 소인수분해로 약수의 개수를 셀 수 있다
  • 삼각수 공식을 사용할 수 있다
  • 서로소인 인수의 곱을 나누어 다룰 수 있다

문제

원문 보기 (영어)

삼각수는 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

예시

예시 1
입력:
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입니다.

예시 2
입력:
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에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

코더마다 가장 좋은 통과 풀이입니다. 더 빠르고, 메모리를 덜 쓰고, 평가가 좋은 풀이가 위에 옵니다.

아직 통과한 풀이가 없습니다. 풀어서 1위를 차지하세요.

다른 사람의 풀이 보기

커뮤니티 솔루션

아직 공개된 풀이가 없습니다. 문제를 풀고 첫 풀이를 공유하세요.