https://atcoder.jp/contests/abc044/tasks/arc060_b
// https://atcoder.jp/contests/abc044/tasks/arc060_b
// 根号分治
// 将数据范围分为两部分处理, 使得拆开成两部分后各部分复杂度均符合要求
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
LL f(LL b, LL n)
{
if (n < b) return n;
else return f(b, n / b) + n % b;
}
void solv()
{
LL n, s, b;
cin >> n >> s;
if (n == s)
{
cout << n + 1 << endl;
return;
}
if (n < s)
{
cout << -1 << endl;
return;
}
// 尝试 b = 2 ~ sqrt n
LL n2 = sqrt(n);
for (b = 2; b <= n2; b ++)
{
if (f(b, n) == s)
{
cout << b << endl;
return;
}
}
// 检查 b = sqrt n ~ n
// 假设 n = pb + q, s = p + q
// p(b-1) = n-s
// 可知 p 的范围为 1 ~ sqrt n, 因而枚举 p进行检查
// 注意 p 从大到小枚举, 如此得到的b才是从小到大
for (int p = n2; p > 0; p --)
{
if ((n-s) % p == 0)
{
b = (n-s) / p + 1;
if (f(b, n) == s)
{
cout << b << endl;
return;
}
}
}
cout << -1 << endl;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T = 1;
// cin >> T;
while (T --)
{
solv();
}
return 0;
}