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

Highly Divisible Triangular Number

Find the first triangular number that has at least d divisors.

배우게 될 내용

  • Count divisors from a prime factorization
  • Use the formula for triangular numbers
  • Split a product of coprime factors

문제

번역본 보기

Triangular numbers count the dots in a triangle of rows 1, 2, 3, ...: T(1) = 1, T(2) = 3, T(3) = 6, and T(k) = k(k + 1) / 2. Walk through them in order and stop at the first one with at least d positive divisors (1 and the number itself count).

Implement highly_divisible_triangular(d).

Counting divisors one by one is too slow for the larger cases. Factor the number instead: if n = p^a × q^b × ..., it has (a + 1)(b + 1)... divisors. Since k and k + 1 share no factor, you can factor them separately.

Input

d: The number of divisors needed.

Output

Return the first triangular number with at least d divisors.

제약 조건

1 ≤ d ≤ 300

예시

예시 1
입력:
d = 4

예상 출력:
expected = 6
입력:
long long d = 4;

예상 출력:
long long expected = 6;
입력:
long d = 4;

예상 출력:
long expected = 6;

설명

1 has one divisor and 3 has two, but 6 has four (1, 2, 3, 6), so the answer is 6.

예시 2
입력:
d = 9

예상 출력:
expected = 36
입력:
long long d = 9;

예상 출력:
long long expected = 36;
입력:
long d = 9;

예상 출력:
long expected = 36;

설명

28 has six divisors and 36 = 2² × 3² has 3 × 3 = 9 (1, 2, 3, 4, 6, 9, 12, 18, 36), so the answer is 36.

접근 방법

먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.

힌트 1

T(k) = k(k + 1) / 2, and k and k + 1 have no common factor.

힌트 2

Halve whichever of k and k + 1 is even, then count the divisors of each part.

힌트 3

The divisor count of a product of coprime numbers is the product of their counts.

예상 복잡도

O(K √K) time for K triangular numbers tried, O(1) extra space

참고 자료

이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

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

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

다른 사람의 풀이 보기

커뮤니티 솔루션

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