Сразу скажу, это единственная задача, которая не вошла в https://codeforces.net/blog/entry/74106, основанный на МОШе, и не зря, ведь там нужно было ифать кучу случаев, и у меня, например, за неё 98 баллов :)
Условие
...
Решение
Первый случай, когда m = 1
Нетрудно заметить, что любое число делится на 1, поэтому спрашивать ничего не надо. Второй случай, когда n = 1
Заметим, что 0 делится на m, а 1 — нет, поэтому придётся задать 1 вопрос. Третий случай, когда m >= b^n
Заметим, что тогда все возможные числа x такие, что 0 < x < m, значит x не делится на m, и спрашивать ничего не надо. Основная идея
Код на Python
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)
Код на C++
#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;
}