Такая задача. Дано число 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
volvo
15.08.2008 16:58
Может и есть... Ты напиши лучше, каким компилятором пользуешься? Ибо если взять FPC, то решение укладывается в 35 строк (Хинт: тип QWord дает тебе возможность безо всякого массива байт работать с 20-значными числами. Еще хинт: быстрее будет не "изобретать новое число", а просто умножать заданное N на все подряд числа от 1 до тех пор, пока все цифры результата не будут нужными, если тебе гарантировали наличие такого числа).
Как результат работы программы: число 7272272220 делится на 512565 нацело (как видишь, работает даже для входных данных больших, чем 500000). Результат получен за 3 сотых секунды. Устраивает такая скорость?
S_lip
15.08.2008 18:19
Спастбо за совет, volvo! Да, использую FPC. Если я тебя правлиьно понял и правильно написал, то вот что должно получиться:
var q:qword; n:longint;
function Not720(q:qword):boolean; begin while q>0 do begin if not ((q mod 10) in [0,2,7]) then exit(true); q:=q div 10; end; exit(false); end;
begin readln(n);
q:=n; while Not720(q) do q:=q+n;
writeln(q); end.
Однако есть числа, для которых этот код работает слишком долго =[. Например: 80411, 199999, 499999...
Кроме того, qword может достигать величины 2^64-1 ~ 2*10^19 (т.е. 19-ти значного числа).
Может, есть еще варианты решения?
volvo
16.08.2008 0:16
Хм... Я тут немного ускорил программу (за счет того, что всего при моем способе возможно 224 = чуть больше 16 с половиной миллионов итераций, а при том, что я предложил раньше - порядка 230, ну ты и сам сказал об этом...) Смотри:
uses windows;
function my_sys(n: integer): qword; var s: qword; count: qword; const radix = 3; digits: array[0 .. pred(radix)] of integer = (0, 2, 7); begin s := 0; count := 1; repeat s := digits[(n mod radix)] * count + s; n := n div radix; count := count * 10; until n = 0;
result := s; end;
const max_n = 500000; var T: dword; n, q: qword; i, delta: integer; begin n := 49999;
T := gettickcount(); // тут небольшая хитрость: если число ближе к концу интервала, чем к началу, // то я иду от конца, т.к. больше шансов, что ответ будет большим. Но это надо // проверить, всегда ли выдается правильный ответ. Может надо идти строго от // начала к концу с Delta = +1 ... if n > max_n div 2 then begin i := (1 shl 24) - 1; delta := -1; end else begin while my_sys(i) < n do inc(i); // пропускаем все числа, которые меньше N delta := 1; end;
repeat if my_sys(i) mod n = 0 then break; inc(i, delta) until false; writeln(my_sys(i), ' : ', n, '':3, 'time = ', gettickcount() - T); end.
А теперь посмотри лог новой программы:
Цитата
270272 : 1312 time = 0 270772020722 : 19999 time = 156 2022070707777 : 49999 time = 343 7022200720227 : 80411 time = 672 270277207207207 : 199999 time = 5531 2020707070077777 : 499999 time = 328
Для сравнения: старая программа выдавала:
Цитата
2022070707777 : 49999 = 40442223 27672
(результатов при n = 499999 и 199999 я просто не дождался)
Итого - ускорение в десятки раз (в среднем - в 50, где-то больше, где-то меньше). Посмотри, может еще что сможешь ускорить, я пока никакого решения алгоритмическим путем, а не перебором, придумать не могу.
Кстати. Чуть не забыл. Если тебе все же хочется работать не с QWord (хотя все результаты по-моему помещаются в QWord), то открывай DRKB и смотри там "Математика, алгоритмы -> Арифметика, системы счисления, комплексные числа -> Очень большие числа -> Огромные числа" модуль для работы с большими числами... Только учти: я здесь убрал всю работу со строками, везде только целочисленные типы. Как только будешь работать с конвертацией "строка -> число" и наоборот - получишь замедление...
S_lip
16.08.2008 17:44
Идея ясна, но если число больше 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. (в это случе это будет 2+9+17+0+33=61; ответ '70272' ). Есть нюансы: если остаток в элементе ноль , то нужно заменить его на n; из элементво одинаковой высоты можно брать одно (или вообше не брать) - т.е. 2 или 7 или 0 (*10^y). Однако при таком подходе тоже приходится перебирать все варианты ( т.е. маскимум 3^20). Поэтому с этой идеей я тоже зашел в тупик.
S_lip
4.05.2013 20:05
Сегодня во сне ко мне явился голос, который сказал, что теперь я знаю решение. Вот оно:
Идея с массивом с остатками от деления на 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).
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.