Делитель числа 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 сотых секунды. Устраивает такая скорость?

[S_lip]

Спастбо за совет, 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-ти значного числа).

Может, есть еще варианты решения?

Сообщение отредактировано: S_lip - 15.08.2008 18:26

[volvo]

Хм... Я тут немного ускорил программу (за счет того, что всего при моем способе возможно 2²⁴ = чуть больше 16 с половиной миллионов итераций, а при том, что я предложил раньше - порядка 2³⁰, ну ты и сам сказал об этом...) Смотри:

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]

Идея ясна, но если число больше 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 17:48

[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 20:42