Делитель числа n, состоящий из цифр 0, 7 и 2. Опции

[S_lip]

Такая задача. Дано число n (0<n<500000). Нужно найти число s, которое делило бы n без остатка и состояло бы только из цифр 7, 2 и 0. s может содердать до 20 знаков. Гарантируется, что число s существует.

Примеры:
n=3 s=27
n=59 s=22007
n=1312 s=270272

Я ничего умнее не придумал, кроме как решить через лоб: взял массиб из 20 байтов. На каждом шаге учеличивал на "1"( т.е. 2 -> 7 -> 20 -> 27 -> 70 ...) и проверял, есть ли остаток при делении на n. Понятно, что в худшем случае придестя увеличивать s 3^20 раз, а это слишком много.

Может, есть какой-нибудь более красивый способ для решения этой задачи?

Источник (я чуть изменил условие): www.lio.lv/olimps/uzdevumi.php?show=18

Сообщение отредактировано: S_lip - 14.08.2008 21:33

[S_lip]

Сегодня во сне ко мне явился голос, который сказал, что теперь я знаю решение. Вот оно:

Идея с массивом с остатками от деления на n хорошая. Но вместо того, чтобы помнить всевозможные (3^20) варианты, мы запоминаем только наименьшие делимые с уникальным остатком.

Пример: если n=61, то 7%61== 2020%61. Мы запоминаем только 7, а 2020 игнорируем.

Вот как мы это делаем:
1. Создаем массив [0..n-1] для всевозможных остатков.
2. Отмечаем нулевой остаток как известный.
3. Затем для каждого следующего знака делителя (длина которого может быть макс 20) проходим через весь список остатков и обновляем непосещенные.
4. Если остаток = 0, то мы нашли победителя.

Пример: во время первой инерации в массиве мы наткнемся только на нулевой остаток. Поэтому к посещенным остаткам добавим (0+2)%61 и (0+7)%61. Например, после 6ой инерации, для каждого посещенного остатка r добавляем остатки (r+2*10^5)%61 и (r+7*10^5)%61.

Чтобы не считать большие 2*10^p можно хранить только их модуль от n (прямо как в пред. посте).

В каждом елементе (=остатке) масива хранятся знак (2 или 7), указатель/индекс предыдущего остака и количество знаков (по ним отпереляем посещен ли уже этот остаток, а также определяем склько нулей нужно добавить перед предыдущим и текущим остатком - ведь в массиве нуль как знак мы учитываем не можем, потому что (r+0*10^p)%n = r%n).

Сообщение отредактировано: S_lip - 4.05.2013 16:42