32291번 - $x$와 $x+1$의 차이
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 670 | 271 | 236 | 44.782% |
문제
초등학생인 철수와 영희는 최근 나눗셈을 배우고 있습니다. 문득 영희는 이런 궁금증이 생겼습니다.
- $998$을 $k$로 나눈 몫과 $999$를 $k$로 나눈 몫이 다르게 되는 $k$는 얼마나 많을까?
영희는 수학을 잘 하는 철수에게 물어봤지만, 철수도 그 답을 몰랐습니다. 이제 여러분이 철수와 영희의 궁금증을 해결해 줍시다.
여러분은 다음 문제를 해결해야 합니다.
- 양의 정수 $x$가 주어질 때, $\left\lfloor{\frac{{x}}{{k}}}\right\rfloor$과 $\left\lfloor{\frac{{x+1}}{{k}}}\right\rfloor$의 값이 다르게 되는 $x$ 이하의 양의 정수 $k$의 값을 모두 찾아 주세요.$^\dagger$
$^\dagger$ 두 양의 정수 $a$와 $b$가 주어질 때, $\left\lfloor{\frac{{a}}{{b}}}\right\rfloor$는 $a$를 $b$로 나눈 몫을 의미합니다.
입력
한 줄에 양의 정수 $x$가 주어집니다. ($1 \le x \le 10^{12}$)
출력
한 줄에 문제의 정답이 되는 $k$의 값을 작은 것부터 순서대로 출력합니다.
모든 입력에 대해 출력해야 하는 값의 개수가 $10\,000$개를 초과하지 않음을 증명할 수 있습니다.
예제 입력 1
998
예제 출력 1
1 3 9 27 37 111 333
예제 출력의 각 $k$에 대응되는 두 몫의 값은 다음과 같습니다.
- $k=1$: $\left\lfloor{\frac{{998}}{{1}}}\right\rfloor=998$, $\left\lfloor{\frac{{999}}{{1}}}\right\rfloor=999$, $998 \neq 999$
- $k=3$: $\left\lfloor{\frac{{998}}{{3}}}\right\rfloor=332$, $\left\lfloor{\frac{{999}}{{3}}}\right\rfloor=333$, $332 \neq 333$
- $k=9$: $\left\lfloor{\frac{{998}}{{9}}}\right\rfloor=110$, $\left\lfloor{\frac{{999}}{{9}}}\right\rfloor=111$, $110 \neq 111$
- $k=27$: $\left\lfloor{\frac{{998}}{{27}}}\right\rfloor=36$, $\left\lfloor{\frac{{999}}{{27}}}\right\rfloor=37$, $36 \neq 37$
- $k=37$: $\left\lfloor{\frac{{998}}{{37}}}\right\rfloor=26$, $\left\lfloor{\frac{{999}}{{37}}}\right\rfloor=27$, $26 \neq 27$
- $k=111$: $\left\lfloor{\frac{{998}}{{111}}}\right\rfloor=8$, $\left\lfloor{\frac{{999}}{{111}}}\right\rfloor=9$, $8 \neq 9$
- $k=333$: $\left\lfloor{\frac{{998}}{{333}}}\right\rfloor=2$, $\left\lfloor{\frac{{999}}{{333}}}\right\rfloor=3$, $2 \neq 3$
노트
입력과 출력이 32비트 정수의 최댓값을 초과할 수 있음에 유의하세요. 값을 저장하기 위해 다음을 사용할 것을 권장합니다.
- C/C++:
long long - Java:
long - Python:
int(별도의 처리를 할 필요가 없습니다.) - 이외의 언어: 언어별 레퍼런스를 참고합니다.
출처
University > 서울과학기술대학교 > STPC 2024 Autumn by Seoultech FLY D번
- 문제를 만든 사람: hjroh0315
- 문제를 검수한 사람: jwpassion1, kiwiyou, penguin1234, ruykun