Делитель числа 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]

Идея ясна, но если число больше 250000 (max_n div 2) и отсчет идет от конца, то нет грарантии, что найденный делитель будет минимальным. Например: n=270000 s=270000 (а прога выдаст 2022270070770000).
Возможно ты в комментрарии имел в виду именно эту проверку. В любом случае, все сводится к тому, что нужно идти от начала.

Эта задача была на Латвийской государственной олимпиаде 1998 года. Я не знаю, был ли тогда тип qword, но компы точно были медленнее =)). Поэтмоу наверняка есть простое решение, которое на современном компе выполнялось бы за очень короткое время (с учетом того, что тогда на работу проги отводилась 1 секунда).

У меня была такая идея: создать массив [1..2,0..19], в котором хранятся остатки от деления на n. Первый столбик соответсвует остаткам при делиталях 2*10^y (т.е. 2, 20, 200 ...), а второй - при 7*10^y.

Код

Массив при n=61
   2   7   10^0
  20   9   10^1
  17  29   10^2
  48  46   10^3
  53  33   10^4
  42  25   10^5
  54   6   10^6
  52  60   10^7
  32  51   10^8
  15  22   10^9
  28  37   10^10
  36   4   10^11
  55  40   10^12
   1  34   10^13
  10  35   10^14
  39  45   10^15
  24  23   10^16
  57  47   10^17
  21  43   10^18
  27   3   10^19

После заполнения массива всего лишь остается сложить некоторые его значения так, чтобы сумма равнялась n.
(в это случе это будет 2+9+17+0+33=61; ответ '70272' ). Есть нюансы: если остаток в элементе ноль , то нужно заменить его на n; из элементво одинаковой высоты можно брать одно (или вообше не брать) - т.е. 2 или 7 или 0 (*10^y). Однако при таком подходе тоже приходится перебирать все варианты ( т.е. маскимум 3^20). Поэтому с этой идеей я тоже зашел в тупик.

Сообщение отредактировано: S_lip - 16.08.2008 13:48