Сразу скажу, это единственная задача, которая не вошла в https://codeforces.net/blog/entry/74106, основанный на МОШе, и не зря, ведь в ней нужно ифать кучу случаев, и у меня, например, 98 баллов :)
Аня сообщает Боре $$$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$$$.
Суммарная сложность О(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;
}