019. Уравнение по основанию

(Время - 1 сек., память - 16 Мб)

Запись AX обозначает, что A есть запись числа в системе счисления по основанию X. Если X>10, то для записи числа используются кроме цифр от 0 до 9 заглавные латинские буквы от A до Z. При этом условии X не может быть больше 36.

Требуется написать программу, которая по заданным A и B найдет решение уравнения AX = B, либо сообщит об отсутствии у него решений.

Входные данные

В первой строке входного файла input.txt записано число A, во второй - число B (1 ≤ B ≤ 107).

Выходные данные

В единственную строку выходного файла output.txt нужно вывести либо наименьшее основание системы счисления, удовлетворяющее уравнению, либо 0, если уравнение не имеет решений.

Пример

input.txt

output.txt

1

A1
161

16

2

201
26

0

Разбор

Вначале по записи числа А определим минимально возможное основание системы счисления. После этого перебором по основаниям системы счисления проверяем выполнение уравнения. Для вычисления значения числа по его цифрам и основанию системы счисления используем схему Горнера.

Программа на Паскале

var

  a, c : string;

  b, z : longint;

  x, l, i : integer;

begin

  assign(input,'input.txt'); reset(input);

  assign(output,'output.txt'); rewrite(output);

  readln(a); read(b);

  c:='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';

  x:=0;

  for i:=1 to length(a) do

    if pos(a[i],c)>x then x:=pos(a[i],c);

  z:=0;

  while z<b do

  begin

    z:=0;

    for i:=1 to length(a) do

      z:=z*x+pos(a[i],c)-1;

    if z=b then write(x);

    x:=x+1

  end;

  if z>b then write(0)

end.

Программа на С

 

Информация о задаче

Автор, источник

 

Олимпиада

Муниципальный этап олимпиады в Ханты-Мансийском АО-Югре, 2008-2009 уч. год, 4-й тур

Тематика

Целочисленная арифметика

Примерная сложность

26%

Ссылки в Интернете

Условие, сдача решения – http://acmu.ru/index.asp?main=task&id_task=526

Наш сайт

Сдача решения –

Тесты – Rar

Задача подготовлена

Автор, дата –  Алексеев А.В., 24.05.2012