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

Спастбо за совет, 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 14:26