Аня сообщает Боре $$$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 \geqslant b^n$$$:

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

Тут есть важный момент, что, чтобы не вычислять $$$b^{10^9}$$$, можно написать $$$b^{min(n, \, 30)}$$$, так как $$$2^{30}$$$ уже $$$> 10^9$$$.

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

Если $$$m < b^n$$$, то $$$\exists \, x$$$ такое что $$$b^{n-1} \leqslant x < b^n$$$ и $$$x \, \vdots \, m$$$. Пусть мы не спросили про $$$k$$$-ый символ.

Если $$$b^{k-1} \, \vdots \, m$$$, то, во-первых, $$$b^t \, \vdots \, m$$$ при $$$t \geqslant k$$$, а во-вторых, нам не важно, какие цифры стоят на местах с $$$k$$$ по $$$n$$$.

Иначе, может быть загадано $$$x$$$, а может $$$x+b^{k-1}$$$ или $$$x-b^{k-1}$$$, и мы не поймём делится оно на $$$m$$$ или нет...

Значит находим бинпоиском по ответу первое $$$k$$$, при котором $$$b^{k-1} \, \vdots \, m$$$.

Четвёртый случай, когда $$$k \geqslant n$$$ или не существует, и $$$b = 2$$$:

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

Иначе:

Нам нужно проверить все индексы $$$< k$$$, и только их, ответ $$$k$$$.

Суммарная сложность $$$O(log(n)^2)$$$ из-за возведения в степень за $$$O(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;
}