...

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

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

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, 179)):
    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;
}