| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 256 MB | 31 | 12 | 11 | 36.667% |
Busy Beaver is given a positive integer $k$ ($1 \le k \le 10^{18}$) written in base $10$. Then, he repeatedly performs the following operation:
Choose a digit in $k$ that is greater than $1$. If $k$ is divisible by that digit, divide $k$ by that digit. Repeat this process on the resulting number until either $1$ is reached or there are no more legal operations. Call $k$ valid if there exists a way to reduce it to $1$ via this operation.
Compute the number of $k$ in the range $1, \dots, N$ that are valid.
The first line of input contains the given integer $N$ ($1 \le N \le 10^{18}$).
Output a single line, with a single integer equivalent to the number of integers from $1$ to $N$ that have a way to reach $1$ using the operation.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 25 | $N \le 10^5$. |
| 2 | 75 | No additional constraints. |
9
9
13
10
In the first test case, all integers from $1$ to $9$ can be divided by themselves to reach $1$, so the answer is $9$.
In the second test case, all integers from $1$ to $9$ are valid, as mentioned in the first test case. $10$, $11$, and $13$ have no digits greater than $1$ that are divisors of themselves, and therefore cannot be reduced to $1$. However, $12$ can be divided by $2$ to get $6$, which can in turn be divided by $6$ to get $1$. Therefore, the numbers $1$ through $9$ and $12$ are valid, giving an answer of $10$.
University > MIT > M(IT)^2 > M(IT)^2 Winter 2025 Tournament > Advanced Round 1 1번