Олимпиады для начинающих: Московская олимпиада, 9 класс, 2020 год

Недавно Маша и Петя изучили в школе системы счисления. Им объяснили, что в повседневной жизни используется система счисления c основанием 10, поэтому все числа состоят из цифр от 0 до 9. Если в такой записи число имеет длину \(k\) и имеет запись вида \(\overline{a_{k-1}a_{k-2}a_{k-3} \ldots a_1a_0}\), то величина числа равна \(a_0 + a_1 \cdot 10^1 + a_2 \cdot 10^2 + a_3 \cdot 10^3 + \ldots + a_{k-1} \cdot 10^{k - 1}\). Здесь \(a_{k-1}\) — это старшая цифра в записи числа, а \(a_0\) — младшая.

Точно таким же образом можно записывать числа в других системах счисления. А именно, если сказать, что число \(b\) — это основание системы счисления, любое неотрицательное целое число может быть записано цифрами со значениями от 0 до \(b - 1\). В такой записи если у числа длина \(k\) и число имеет запись вида \(\overline{a_{k-1}a_{k-2}a_{k-3} \ldots a_1a_0}\), то величина числа равна \(a_0 + a_1 \cdot b^1 + a_2 \cdot b^2 + a_3 \cdot b^3 + \ldots + a_{k-1} \cdot b^{k - 1}\). При этом, если у числа длина больше 1, то старшая цифра не должна равняться 0, то есть, если \(k > 1\), то \(a_{k-1} > 0\). Но если длина равна 1, то число может состоять из единственной цифры 0.

Например число \(21\) из системы счисления с основанием 10 представляется как:

• \(1;0;1;0;1\) в системе счисления с основанием \(2\)
• \(2;1;0\) в системе счисления с основанием \(3\)
• \(4;1\) в системе счисления с основанием \(5\)
• \(1;10\) в системе счисления с основанием \(11\)
• \(1;3\) в системе счисления с основанием \(18\)
• \(21\) в системе счисления с основанием \(37\)

Здесь цифры в записи числа в недесятичных системах счисления для удобства разделены точкой с запятой. Обратите внимание, что в этих примерах, 10 или 21 — это тоже цифры соответствующих систем счисления.

Чтобы лучше усвоить системы счисления, Маша и Петя решили поиграть в такую игру: в начале игры Петя называет Маше три числа: \(b\), \(n\) и \(m\). После этого Маша загадывает некоторое неотрицательное целое число в системе счисления с основанием \(b\), которое имеет длину \(n\). Теперь Петя должен понять, делится ли загаданное Машей число на \(m\) нацело. Для этого он может один раз спросить у Маши, чему равны цифры на определённых позициях в загаданном Машей числе в системе счисления с основанием \(b\). Помогите Пете найти минимальное число позиций, про которые ему придётся спросить, чтобы однозначно определить, делится загаданное Машей число на \(m\) или нет.