Здравствуйте. Подскажите кто-нибудь как найти сумму цифр всех чисел на заданном интервале от A до B. А и В до 10^9 степени. Спасибо.
Здравствуйте. Подскажите кто-нибудь как найти сумму цифр всех чисел на заданном интервале от A до B. А и В до 10^9 степени. Спасибо.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 153 |
| 2 | nik_exists | 151 |
| 3 | maroonrk | 150 |
| 4 | maspy | 149 |
| 5 | AmShZ | 146 |
| 6 | Um_nik | 143 |
| 7 | Errichto | 139 |
| 8 | adamant | 135 |
| 9 | BledDest | 134 |
| 10 | cry | 130 |
| Название |
|---|



Чтобы решить задачу, нужно заметить несколько важных моментов. Первое: пусть
f(A)— сумма цифр всех чисел от 1 доA. Тогда ответ на задачу этоf(B) - f(A - 1). Теперь научимся считатьf(A). Для начала посчитаем кол-во цифрlen(A)в числеА. Теперь прибавим к ответу сумму цифр всех чиселx, таких, чтоlen(x) < len(A). Это можно сделать, учтя сразу все числа одной длины. Делается как-то комбинаторно одной формулой, остается на рассмотрение читателю. Теперь посмотрим на цифру, отвечающую за наибольший разряд —A[0]числаА. В ответ точно войдут суммы цифр всех таких чиселх, чтоlen(x) == len(A)иx[0] < A[0]. Тогда перебрав цифру или учтя сразу все цифры< A[0]и, опять же, посчитав суммарное кол-во цифр в последовательностях цифр длиныlen(A) - 1, мы можем учесть все числа такой же длины, что иА, но имеющих первую цифру меньше, чем уА. Остались неучтенными только те числах, такие, чтоlen(x) == len(A) && x[0] == A[0]. Теперь у нас есть фиксированный префикс числа, состоящий изA[0]и задача, почти аналогичная тому, чтобы найти кол-во чисел, равных по длинеАи имеющих нулевую цифру равную нулевой цифреА. Повторим решение и перейдем к совпадающему префиксуA[0],A[1]. Будем повторять это, пока совпадающим префиксом не станет само числоA.Не уверен на 100%, что решение работает, но звучит весьма убедительно. Довольно неприятная задача, как и почти любая задача, связанная с цифрами. В особенности, ДП по цифрам.