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

Хм... Я тут немного ускорил программу (за счет того, что всего при моем способе возможно 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 и смотри там "Математика, алгоритмы -> Арифметика, системы счисления, комплексные числа -> Очень большие числа -> Огромные числа" модуль для работы с большими числами... Только учти: я здесь убрал всю работу со строками, везде только целочисленные типы. Как только будешь работать с конвертацией "строка -> число" и наоборот - получишь замедление...