Делитель числа 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 - 15.08.2008 1:33

[volvo]

Может и есть... Ты напиши лучше, каким компилятором пользуешься? Ибо если взять FPC, то решение укладывается в 35 строк (Хинт: тип QWord дает тебе возможность безо всякого массива байт работать с 20-значными числами. Еще хинт: быстрее будет не "изобретать новое число", а просто умножать заданное N на все подряд числа от 1 до тех пор, пока все цифры результата не будут нужными, если тебе гарантировали наличие такого числа).

Как результат работы программы: число 7272272220 делится на 512565 нацело (как видишь, работает даже для входных данных больших, чем 500000). Результат получен за 3 сотых секунды. Устраивает такая скорость?