루마니아 체

시간 제한2초메모리 제한2048 MB

요약

정수 t가 주어질 때, 내부 루프의 실행 횟수가 t 이하인 가장 큰 n을 구합니다. 이 횟수는 i가 1부터 n까지일 때 floor(n/i)을 모두 더한 값입니다.

난이도: 보통10점 중 6점
유형: 수학, 이분 탐색, 정수론
정답자: 아직 제출이 없습니다

문제

Petrică Cercel의 아들 Ionuț Cercel은 "Made in Romania"라는 큰 히트곡 이후 음악에서 이룰 수 있는 것은 모두 이루었다.

이제 그는 경쟁 프로그래밍에 관심을 갖게 되었다. Phapos에서 열리는 훈련 캠프를 준비하던 중, 그는 "The Romanian Sieve"라는 개념을 접했다. 이 개념은 아래 코드로 요약할 수 있다.

    int64_t iters = 0;
    for (int64_t i = 1; i ≤ n; i++) {
        for (int64_t j = i; j ≤ n; j += i) {
            max_div[j] = i;
            iters++;
        }
    }

호기심 많은 Ionuț은 스스로에게 묻는다. "정수 $t$ 가 주어졌을 때, 루마니아 체 알고리즘을 실행한 뒤 iters $\leq t$ 를 만족하는 $n$ 의 최댓값은 무엇인가?" 이 질문에 답하도록 도와달라.

입력

첫째 줄에 정수 $t$ ( $1 \leq t \leq 3 \cdot 10^{13}$ )가 주어진다.

출력

알고리즘을 실행한 뒤 iters $\leq t$ 를 만족하는 $n$ 의 최댓값을 정수 하나로 출력한다.

예제2

예제 1
입력
```
11
```
예상 출력
```
5
```
예제 2
입력
```
2846010382
```
예상 출력
```
149946143
```