Сразу скажу, это единственная задача, которая не вошла в https://codeforces.net/blog/entry/74106, основанный на МОШе, и не зря, ведь там нужно было ифать кучу случаев, и у меня, например, за неё 98 баллов :)
Аня загадывает 3 числа $$$2 \leqslant b \leqslant 10^9$$$,
$$$n \leqslant 10^9$$$ и $$$m \leqslant 10^9$$$,
а потом число, длины n в b-ичной системе счисления,
причём если $$$n \ne 1$$$, то его старшая цифра не 0.
Вам нужно сказать, про сколько позиций придётся спросить,
какая на них цифра, чтобы точно понять,
делится это число на 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;
}