problem link [http://www.codeforces.com/contest/248/problem/B]
→ Обратите внимание
До соревнования
WorldQuant Round 1 (Codeforces Round 1128, Div. 1 + Div. 2)
3 дня
Зарегистрироваться »
WorldQuant Round 1 (Codeforces Round 1128, Div. 1 + Div. 2)
3 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | jiangly | 3670 |
| 3 | Kevin114514 | 3657 |
| 4 | maroonrk | 3355 |
| 5 | Um_nik | 3353 |
| 6 | squareOf105 | 3346 |
| 7 | tourist | 3343 |
| 8 | strapple | 3324 |
| 9 | heuristica | 3322 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | AmShZ | 143 |
| 5 | Um_nik | 141 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | BledDest | 134 |
| 9 | maroonrk | 133 |
| 10 | qwexd | 130 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 14.10.2026 23:26:11 (f1).
Десктопная версия, переключиться на мобильную.
При поддержке
The least common multiple of this numbers (2,3,5,7) is 210. So you are asked to find smallest n-digit number, which is divisible by 210.
Let's take smallest n-digit number X=(10^(n-1)). We can consider all numbers from X to X+210 and choose the one, which is divisible* by 210. Of course that one will be the answer.
*Since X is very large (maximum 10^5 digits), you've got to use "long integer arithmetics".
Thanks a lot. My solution in python runned out of time using same approach.
Hers is O(n) solution:
Let dp[i] be the remainder of 10^i when divided by 210. dp[0]=1; dp[i+1]=(dp[i]*10)mod 210;
We can precalculate dp[0...10^5] in O(10^5) time.
Let's take smallest n-digit number (10^(n-1)). It gives dp[n-1] as a remainder when divided by 210. Therefore (10^(n-1))-dp[n-1]+210 is divisible by 210.
So, 10^(n-1)-dp[n-1]+210 is the answer.
The answer will be a number of following type :
First digit will be equal to 1.
The number obtained by last three digits together should be equal to 210-dp[n-1].
all other digits will be equal to 0.
Thanks a lot, this sure helps.