...

Первый случай, когда 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)