Аня сообщает Боре $$$3$$$ числа $$$b, n, m$$$ ($$$2 \leqslant b \leqslant 10^9$$$, $$$1 \leqslant n, m \leqslant 10^9$$$), а потом загадывает число, длины $$$n$$$ в $$$b$$$-ичной системе счисления, причём если $$$n \ne 1$$$, то его старшая цифра не $$$0$$$.

Боря за $$$1$$$ действие может спросить, какая цифра стоит в этом числе на $$$i$$$-ой позиции.

Выведите, сколько действий Боре придётся совершить, чтобы гарантированно узнать, делится это число на $$$m$$$ или нет.

Первый случай, когда m = 1

Нетрудно заметить, что любое число делится на 1, поэтому спрашивать ничего не надо.

Второй случай, когда n = 1

Заметим, что 0 делится на m, а 1 — нет, поэтому придётся задать 1 вопрос.

Третий случай, когда m >= b^n

Заметим, что тогда все возможные числа > чем 0 и < чем m, значит не делятся на m, и спрашивать ничего не надо.

Основная идея:

Если $$$m < b^n$$$, то $$$\exists \, x$$$ такое что

$$$b^{n-1} \leqslant x < b^n$$$ и $$$x \, \vdots \, m$$$.

Тогда если мы не спросили про k-ый символ и $$$b^{k-1}$$$ не $$$\vdots \, m$$$,

может быть загадано x, а может $$$x+b^{k-1}$$$ или $$$x-b^{k-1}$$$,

и мы не поймём делится оно на m или нет...

А если $$$b^{k-1} \, \vdots \, m$$$, то, во-первых, $$$b^t \, \vdots \, m$$$ при

$$$(t \geqslant k)$$$, а во-вторых,\ нам не важно, какие цифры стоят на местах с k по n.

Значит нам надо найти первое n, при котором $$$b^{n-1} \, \vdots \, m$$$,

и проверить все меньшие индексы, то есть всего n штук.

А n мы ищем бинпоиском по ответу.

Тут есть 1 нюанс: если $$$k \geqslant n$$$ или не существует, и b = 2.

Тогда первая цифра точно будет 1, её можно не спрашивать, ответ n-1.

Суммарная сложность О(log(n)).

b, n, m = int(input()), int(input()), int(input())
if m == 1:
    print(0)
elif n == 1:
    print(1)
elif m >= pow(b, min(n, 30)):
    print(0)
else:
    l, r = -1, n
    while r-l > 1:
        m1 = (l+r)//2
        if pow(b, m1, m) == 0:
            r = m1
        else:
            l = m1
    if b == 2 and r == n:
        print(n-1)
    else:
        print(r)

#include<bits/stdc++.h>
#define int long long
#define p pair<int, int>
#define endl '\n'

using namespace std;

int pow1(int x, int y, int z){
    if (y == 0){
        return 1;
    }
    if (y % 2 == 0){
        return pow1(x*x % z, y/2, z);
    }
    return pow1(x, y-1, z)*x % z;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int b, n, m;
    cin >> b >> n >> m;
    if (m == 1){
        cout << 0 << endl;
    }else if (n == 1){
        cout << 1 << endl;
    }else if (m >= (int)pow(b, min(n, 30LL))){
        cout << 0 << endl;
    }else{
        int l = -1, r = n;
        while (r-l > 1){
            int m1 = (l+r)/2;
            if (pow1(b, m1, m) == 0){
                r = m1;
            }else{
                l = m1;
            }
        }
        if (b == 2 && r == n){
            cout << n-1 << endl;
        }else{
            cout << r << endl;
        }
    }
    return 0;
}