| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Делимость и сумма цифр числа |
| Автор: Assasin92 27.2.2012, 16:54 |
| Здравствуйте. Есть задача: на вход поступают числа A, B, S, T, k, где 1 <= A, B <= 10^19; 1 <= S, T <= 162; 2 <= k <= 100. Нужно найти все числа, которые находятся на интервале [A, B], имеют сумму цифр, принадлежащих интервалу [S, T] и в то же время делятся на k без остатка. Можно, конечно, перебирать все числа, делящиеся на k и смотреть сумму их цифр, но это будет очень долго. Поэтому хочу спросить, можно ли как-то связать сумму цифр с делимостью на k, или хотя бы считать сумму цифр не применяя всё время функцию, которая находит эту сумму вычисляя остаток от деления числа на степени 10? |
| Автор: Akina 27.2.2012, 17:02 | ||||
В общем случае нет.
Применяя методы работы, используемые в примитивных реализациях длинной арифметики (хранить число как поразрядный массив цифр), можно сильно ускорить процесс. |
| Автор: Assasin92 27.2.2012, 17:49 | ||
Да, знаю, но на тест даётся всего 1 секунда. Даже если использовать длинную арифметику такой скорости работы не добиться. А может можно за одну-две итерации найти сумму цифр следующего числа, принадлежащего [S, T], зная сумму цифр предыдущего с суммой цифр из этого же отрезка? То есть, например, если взять промежуток от 17 до 26: 17: 089, 098; //2 числа 179, 188, 197; //3 числа 269, 278, 287, 296; //4числа и т. д. 18: 99; //новый 189, 198; //2 числа с суммой цифр 17, к которым я добавил 1 в разряд сотен 279, 288, 237; //3 числа -//- 339, 378, 387, 396; 4 числа -//- Есть сложности при переходе на старший разряд(есть условия, когда добавление единицы даст число с меньшей суммой + если интервал меньше n*3 и больше (n+k) * 3, то тоже не понятно, как действовать при подобном быстром поиске суммы цифр числа). |
| Автор: Akina 27.2.2012, 18:00 | ||
a=1 b=10^19 s=1 t=162 k=2 Даже при всей очевидности ответа 1 секунды не хватит не то что на вывод - даже на безалгоритмическую генерацию 5*10^18 чётных чисел. Можете смело говорить, что с учётом ограничения по времени в общем случае задача не решается. |
| Автор: Assasin92 27.2.2012, 18:04 |
| Извиняюсь, надо найти не конкретно числа, а их количество. |
