Problem:
 Score : 500 points    Problem Statement For integers b (b \geq 2) and n (n \geq 1) , let the function f(b,n) be defined as follows:   f(b,n) = n , when n < b  f(b,n) = f(b,\,{\rm floor}(n / b)) + (n \ {\rm mod} \ b) , when n \geq b   Here, {\rm floor}(n / b) denotes the largest integer not exceeding n / b ,
and n \ {\rm mod} \ b denotes the remainder of n divided by b .  Less formally, f(b,n) is equal to the sum of the digits of n written in base b .
For example, the following hold:   f(10,\,87654)=8+7+6+5+4=30  f(100,\,87654)=8+76+54=138   You are given integers n and s .
Determine if there exists an integer b (b \geq 2) such that f(b,n)=s .
If the answer is positive, also find the smallest such b .      Constraints  1 \leq n \leq 10^{11}  1 \leq s \leq 10^{11}  n,\,s are integers.         Input The input is given from Standard Input in the following format:  n  s       Output If there exists an integer b (b \geq 2) such that f(b,n)=s , print the smallest such b .
If such b does not exist, print -1 instead.        Sample Input 1 87654
30      Sample Output 1 10       Sample Input 2 87654
138      Sample Output 2 100       Sample Input 3 87654
45678      Sample Output 3 -1       Sample Input 4 31415926535
1      Sample Output 4 31415926535       Sample Input 5 1
31415926535      Sample Output 5 -1

Solution (Python):
from math import sqrt


def f(b, n):
    if n < b:
        return n
    else:
        return f(b, n//b) + n % b


def divisors(P):
    res = set([])
    for i in range(1, P+1):
        if i**2 > P:
            break
        else:
            if P % i == 0:
                res.add(i)
                res.add(P//i)
    return res


def main():
    N = int(input())
    S = int(input())
    res = 10**18
    if N <= 10**6:
        for b in range(2, N+2):
            if f(b, N) == S:
                res = b
                break
        if res < 10**18:
            print(res)
        else:
            print(-1)
            return

    else:
        
        for b in range(2, 10**6+2):
            if f(b, N) == S:
                res = b
                break
        if res < 10 ** 18:
            print(res)
            return
        else:
            if N < S:
                print(-1)
                return
            elif N == S:
                print(N+1)
                return
            else:
                div = divisors(N-S)
                for y in div:
                    sub_res = y + 1
                    if f(sub_res, N) == S:
                        res = min(res, sub_res)
                        
                if res < 10**18:
                    print(res)
                else:
                    print(-1)
                return

if __name__ == "__main__":
    main()

Solution (Python):
import math
def digit(b, n):
    if n < b:
        return n
    else:
        return digit(b, math.floor(n/b)) + n % b

n, s = int(input()), int(input())  

if n == s:
    print(n+1)
    exit()

if n < s:
    print(-1)
    exit()

for i in range(2, int(math.sqrt(n)) + 2):
    if digit(i, n) == s:
        print(i)
        exit()

for p in range(1,int(math.sqrt(n)))[::-1]:
    q = s - p
    b = (n-s)//p +1
    if 1 <= p < b and 0 <= q < b and (n - s)%p == 0:
        if digit(b, n) == s:
            print(b)
            exit()
print(-1)

Solution (Python):
import math

n = int(input())
s = int(input())
ans = -1
if n > s:
    sqrt_n = math.ceil(math.sqrt(n))
    for b in range(2, sqrt_n + 1):
        m = n
        f = 0
        while m >= b:
            f += (m % b)
            m //= b
        f += m
        if f == s:
            ans = b
            break
    b = sqrt_n
    if ans == -1:
        for p in range(sqrt_n - 1, 0, -1):
            if (n - s) % p == 0:
                b = (n - s) // p + 1
            if n % b + n // b == s:
                ans = b
                break
elif n == s:
    ans = n + 1
print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()

def main():
    """
    nのオーダーを見てb < √nまで半分全探索しようという気持ちになるのか・・・？
    そうだとしても√n < bの場合の考察もやや技巧的に思われるが、
    とりあえず√nで切る方策はある種の定石として覚えておくことにする。
    あとは解説pdf参照。
    """
    n = int(input())
    s = int(input())
    if n < s:
        print(-1)
        return
    if n == s:
        print(n + 1)
        return
    for b in range(2, int(n ** 0.5) + 1):
        val = 0
        num = n
        while num >= b:
            val += num % b
            num //= b
        val += num
        if val == s:
            print(b)
            return
    for p in range(int(n ** 0.5), 0, -1):
        if (n - s) % p != 0: continue
        b = (n - s) // p + 1
        val = 0
        num = n
        while num >= b:
            val += num % b
            num //= b
        val += num
        if val == s:
            print(b)
            return
    print(-1)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
def yakusu(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())
def NIJIGEN(H): return [list(input()) for i in range(H)]
N=int(input())
K=int(input())
if N==K:
  print(N+1)
  exit()
if N<K:
  print(-1)
  exit()
L=list()
setL=set()

L=yakusu(N-K)
L=[i+1 for i in L]
for i in L:
  ans=0
  m=N
  while True:
    if m<i:
      ans+=m
      break
    else:
      ans+=m%i
      m=m//i
  if ans==K:
    print(i)
    exit()
print(-1)

Solution (Python):
n, s = int(input()), int(input())

f = lambda b,n:n if n < b else n%b + f(b,n//b)
import math
ans = math.inf
if n == s: ans = n+1
for b in range(2,math.ceil(math.sqrt(n))+1): 
    if f(b,n) == s:
        ans = b; break
else:
    for p in range(1,math.ceil(math.sqrt(n))): 
        b = (n-s)/p+1
        if b > 1 and b == int(b) and f(b,n) == s:
           ans = min(ans,int(b))
if ans == math.inf: ans = -1
print(ans)

Solution (Python):
def function(b, n):
    if n < b:
        return n
    else:
        return function(b, n//b) + n % b
from math import sqrt
def divs(n):
  d=[]
  for x in range(1,int(sqrt(n))+1):
    if n%x==0:
      d.extend([x,n//x])
  d=list(set(d))
  d.sort()
  return d

def main():
    n = int(input())
    s = int(input())

    if n < s:
        return("-1")
    elif n == s:
        return(n+1)
    else:
        ds = divs(n - s)
        for x in ds:
            if s == function(x+1,n):
                return(x+1)
        else:
            return("-1")

print(main())

Solution (Python):
import sys
import itertools

import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines



import sys
import itertools

import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


N = int(input())
S = int(input())

def f(b, n):
    if n < b:
        return n
    return f(b, n // b) + n % b

MAX = 10 ** 6
for b in range(2, MAX + 1):
    res = f(b, N)
    if res == S:
        print(b)
        exit()
x = N - S
if x < 0:
    print(-1)
elif x == 0:
    print(N + 1)
else:
    ans = -1
    for p in range(1, MAX + 1):
        if x % p == 0:
            b = (x // p) + 1
            if b > MAX and N // b == p:
                ans = b
    print(ans)

Solution (Python):
import math
n = int(input())
s = int(input())

if s == n:
    print(n + 1)
    exit()
elif s > n:
    print(-1)
    exit()

for i in range(2, math.floor(math.sqrt(n)) + 1):
    new_n = n
    remain = 0
    while new_n > 0:
        remain += new_n % i
        new_n //= i

    if remain == s:
        print(i)
        exit()

for i in range(math.floor(math.sqrt(n)) + 1, 0, -1):
    b = (n - s) // i + 1
    st = n % b + n // b
    if n // b != b and st == s:
        print(b)
        exit()

print(-1)

Solution (Python):
def f(b,n):
  if 0<n:
    return n%b+f(b,n//b)
  else:
    return 0

n = int(input())
s = int(input())

for i in range(2,5**8):
  if f(i,n)==s:
    print(i)
    exit()

for i in range(n-s>>18,0,-1):
  if f((n-s)//i+1,n)==s:
    print((n-s)//i+1)
    exit()

if n==s:
  print(n+1)
else:
  print(-1)

Solution (Python):
import sys
def I(): return int(sys.stdin.readline().rstrip())

N,s = I(),I()


def digit_sum(b,n):  
    res = 0
    while n > 0:
        res += n % b
        n //= b
    return res


M = int(N**.5)+1
for b in range(2,M+1):
    if digit_sum(b,N) == s:
        print(b)
        break
else:  
    ans = 10**12
    for q in range(1,M):
        r = s-q
        if (N-r) % q == 0:
            b = (N-r)//q
            if M < b <= N and 0 <= r < b:
                ans = min(ans,b)
    if N == s:  
        ans = min(ans,N+1)
    print(ans if ans != 10**12 else -1)

Solution (Python):
def func(b, n):
    res = 0
    while n > 0:
        res += n % b
        n //= b
    return res


def solve():
    n = int(input())
    s = int(input())

    if n == s:
        return n + 1
    elif n < s:
        return -1

    for b in range(2, n + 1):
        if b**2 > n:
            break
        if func(b, n) == s:
            return b

    b_cand = []
    for p in range(1, n + 1):
        if p**2 > n:
            break
        b = (n - s) // p + 1
        if b > 1:
            b_cand.append(b)
    b_cand = b_cand[::-1]

    for b in b_cand:
        
        if func(b, n) == s:
            return b

    return -1


ans = solve()
print(ans)

Solution (Python):
def divisor(n):
    divisors = []
    i = 1
    while i * i < n:
        if n % i == 0:
            divisors.append(i)
            divisors.append(n // i)
        i += 1
    if i * i == n:
        divisors.append(i)
    divisors.sort()
    return divisors

n = int(input())
s = int(input())
if n == s:
    print(n + 1)
    exit()
if n < s:
    print(-1)
    exit()
sr = int(n ** 0.5)
for b in range(2, sr + 1):
    m = n
    a = 0
    while m:
        a += m % b
        m //= b
    if a == s:
        print(b)
        exit()
for d in divisor(n - s):
    b = d + 1
    if b <= sr:
        continue
    q = (n - s) // d
    r = n % b
    if q + r == s:
        print(b)
        exit()
print(-1)

Solution (Python):
import math

n = int(input())
s = int(input())


r = 0

if n == s:
    print(n + 1)
    exit()
elif n < s:
    print(-1)
    exit()

sq = int(math.sqrt(n))



for i in range(2, sq+1):
    nt = n
    st = 0

    while nt > 0:
        st += nt % i
        nt //= i

    if st == s:
        print(i)
        exit()
    

for i in range(sq+1, 0, -1):
    b = (n - s) // i + 1
    
    st = n % b + n // b

    if n // b != b and st == s:
        print(b)
        exit()

print(-1)

Solution (Python):
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, S = [int(input()), int(input())]


def solve1():
    i = 2
    while i * i <= N:
        if ok(i, N, S):
            return i

        i += 1

    return 1 << 60


def solve2():
    i = 1
    ret = 1 << 60
    while i * i <= N:
        b = (N - S) // i + 1
        if ok(b, N, S):
            ret = min(ret, b)
        i += 1

    return ret


def ok(b, N, S):
    if b <= 1:
        return False

    s, n = 0, N
    while n > 0:
        s += n % b
        n //= b

    return s == S



def solve():
    if S == N:
        return N + 1
    ret = min(solve1(), solve2())
    return ret if ret != 1 << 60 else -1


print(solve())

Solution (Python):
import copy
n=input()
s=input()
ln=len(n)
ls=len(s)
n=int(n)
s=int(s)
if n==s:
    print(n+1)
elif n<s:
    print(-1)
else:
    for b in range(2,pow(10,6)+1):
        N = copy.deepcopy(n)
        f = 0
        while N >= b:
            f += N % b
            N = N // b
        f += N
        if f == s:
            print(b)
            exit()
    ans=-1
    for p in range(1,pow(10,6)+1):
        if (n-s)%p==0:
            b=(n-s)//p+1
        N = copy.deepcopy(n)
        f = 0
        while N >= b:
            f += N % b
            N = N // b
        f += N
        if f == s:
            ans=b
    print(ans)

Solution (Python):
from math import sqrt

def divs(n):
  d=[]
  for x in range(1,int(sqrt(n))+1):
    if n%x==0:
      d.extend([x,n//x])
  d=list(set(d))
  d.sort()
  return d

def f(b,n):
  if n<b:
    return n
  else:
    return f(b,n//b)+(n%b)

n=int(input())
s=int(input())

if n<s:
  print(-1)
  exit()
elif n==s:
  print(n+1)
  exit()
else:
  ds=divs(n-s)
  for x in ds:
    if s==f(x+1,n):
      print(x+1)
      exit()
print(-1)

Solution (Python):
import sys
import math

def divlist(n):
   sl=[]
   ll=[]
   for x in range(1,int(math.sqrt(n))+1):
       if n%x==0:
           sl.append(x)
           ll.append(n//x)
   ll.reverse()
   sl.extend(ll)
   return sl

def f(b,n):
    if n<b:
        return n
    else:
        return f(b,n//b)+(n%b)

def main(n,s):
    if n<s:
        return print(-1)
    elif n==s:
        return print(n+1)
    else:
        dl=divlist(n-s)
        for x in dl:
            if s==f(x+1,n):
                return print(x+1)
        return print(-1)

n=int(sys.stdin.readline().strip())
s=int(sys.stdin.readline().strip())

main(n,s)

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(readline())
    s = int(readline())

    if s > n:
        print(-1)
        sys.exit()
    if s == n:
        print(n + 1)
        sys.exit()

    for i in range(2, n):
        k = i ** 2
        if k > n:
            break
        x = n
        cur = 0
        while x > 0:
            cur += x % i
            x = x // i

        if cur == s:
            print(i)
            sys.exit()

    ans = INF
    for i in range(1, n):
        k = i ** 2
        if k >= n:
            break
        if (n - s) % i == 0:
            b = (n-s) // i + 1
            p = n // b
            q = n % b
            if p + q == s:
                ans = min(ans,b)

    if ans == INF:
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import math


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def f(b, n):
    S = 0
    while n != 0:
        S += n%b
        n //= b
    return S


def solve():
    """
    87654
    138
    -----
    100

    87654
    45678
    -----
    -1

    """
    n = read_int()
    s = read_int()
    for b in range(2, math.ceil(math.sqrt(n))+1):
        if f(b, n) == s:
            return b
    """
    16

    4
    if b>math.sqrt(n) then n=pb+q, p, q < b
                           s=p+q
    n-s=p*(b-1), b-1 >= p
    """
    if n-s < 0:
        return -1
    if n == s:
        return n+1
    for p in range(math.ceil(math.sqrt(n-s)), 0, -1):
        if (n-s)%p == 0 and f((n-s)//p+1, n) == s:
            return (n-s)//p+1
    return -1


if __name__ == '__main__':
    
    
    print(solve())

Solution (Python):
n=int(input())
s=int(input())
if s>n:
  print(-1)
elif s==n:
  print(n+1)
else:
  
  for b in range(2,int(n**0.5)+1):
    tmp=0
    n0=n
    while n0>0:
      tmp+=n0%b
      n0//=b
    if tmp==s:
      print(b)
      exit()
  
  for p in range(int(n**0.5)+1,0,-1):
    b=(n-s)/p+1
    if not b.is_integer():continue
    b=int(b)
    tmp=0
    n0=n
    while n0>0:
      tmp+=n0%b
      n0//=b
    if tmp==s:
      print(b)
      exit()
  print(-1)

Solution (Python):
n = int(input())
s = int(input())
if s == n:
    print(n+1)
    exit()
if s > n%2+n//2:
    print(-1)
    exit()
    

ans = float("INF")
for i in range(2,int(n**0.5)+1):
    x = n
    count = 0
    while x >= i:
        count += x%i
        x //= i
    if count + x == s:
        print(i)
        exit()
now = 2
li = int(n**0.5)+1
while True:

    x = n//now
    if x < li:
        break
    count = 0
    y = n
    while y >= x:
        count += y%x
        y //= x
    count += y
    if count <= s and (s-count)%now == 0:
        z = x-n//(now+1)
        if (s-count)//now < z:
            ans = x-(s-count)//now
    now += 1



print(min(ans,n-s+1))

Solution (Python):
n = int(input())
s = int(input())
if s == 1 and n == 1:
    print(2)
    exit()
if s > n:
    print(-1)
    exit()
if n%2 == 0 and n > s > n//2:
    print(-1)
    exit()
if n%2 == 1 and n > s > n//2+1:
    print(-1)
    exit()

ans = float("INF")
for i in range(2,int(n**0.5)+1):
    x = n
    count = 0
    while x >= i:
        count += x%i
        x //= i
    if count + x == s:
        print(i)
        exit()
now = 2
li = int(n**0.5)+1
while True:

    x = n//now
    if x < li:
        break
    count = 0
    y = n
    while y >= x:
        count += y%x
        y //= x
    count += y
    if count <= s and (s-count)%now == 0:
        z = x-n//(now+1)
        if (s-count)//now < z:
            ans = x-(s-count)//now
    now += 1

if s == n:
    print(min(ans,n+1))
else:
    print(min(ans,n-s+1))

Solution (Python):
n = int(input())
s = int(input())
def f(b, n):
  if n < b:
    return n
  return f(b, n//b) + n%b
if n == s:
  print(n+1)
  exit()
U = int(n**0.5)+100
for b in range(2, U+1):
  if f(b, n) == s:
    print(b)
    exit()
for p in range(U-1, 0, -1):
  if (n-s)%p:
    continue
  b = (n-s)//p + 1
  if b < 2:
    continue
  if f(b, n) == s:
    print(b)
    exit()
print(-1)

Solution (Python):
import sys
n=int(input())
s=int(input())

if n==s:
  print(n+1)
  sys.exit(0)

def f(b,n):
  ret=0
  while n:
    ret+=n%b
    n//=b
  return ret

for b in range(2,int(n**0.5)+1):

  ss=f(b,n)
  if ss==s:
    print(b)
    sys.exit(0)


for p in range(int((n-1)**0.5),0,-1):
  q=s-p
  b=(n-q)//p
  if q<0 or b<=q or b<2 or (n-q)%p!=0:
    continue
    
  
  ss=f(b,n)
  if ss==s:
    print(b)
    sys.exit(0)
    
print(-1)

Solution (Python):
n = int(input())
s = int(input())

import math
def f(b, n):
    
    if n<b:
        return n
    else:
        x = f(b, n//b) + n%b
        return x
ans = 0
if n<s:
    print(-1)
    exit()
if n==s:
    print(n+1)
    exit()
for b in range(2,int(math.sqrt(n))+500):
    if f(b, n) == s:
        ans = b
        print(ans)
        exit()
for p in range(int(math.sqrt(n)), 0, -1):
    if (n+p-s) %p == 0:
        
        if f((n+p-s)//p, n) == s:
            print((n+p-s)//p)
            exit()


print(-1)

Solution (Python):
N=int(input())
S=int(input())
res = 0
for i in range(2,int(N**0.5)+1):
    tmp = N
    tmp2 = 0
    while tmp > 0:
        tmp2 += tmp%i
        tmp = tmp // i
    if tmp2==S:
        res = i
        break
if res == 0:
    for i in range(int(N**0.5)+1,0,-1):
        b = (N-S)//i + 1
        if i*(b-1)+S != N:
            continue
        tmp = N
        tmp2 = 0
        if b<=1:
            continue
        while tmp > 0:
            tmp2 += tmp % b
            tmp = tmp // b
        if tmp2 == S:
            res = b
            break
if N==S:
    print(N+1)
elif res==0 or N<S:
    print(-1)
else:
    print(res)

Solution (Python):
def solve(n, s):
    if n < s:
        return -1
    if n == s:
        return n + 1

    sqn = int((n - 1) ** 0.5) + 1
    
    for b in range(2, sqn + 1):
        tmp = 0
        k = n
        while k > 0:
            d, m = divmod(k, b)
            tmp += m
            k = d
        if tmp == s:
            return b
    
    for p in range(sqn - 1, 0, -1):
        b, m = divmod(n - s, p)
        if m != 0:
            continue
        b += 1
        if p + n % b == s:
            return b
    return -1


n = int(input())
s = int(input())
print(solve(n, s))

Solution (Python):
from math import sqrt


def f(b, n, s):
    cnt = 0
    while n > 0:
        cnt += n % b
        n //= b
    return cnt == s


N = int(input())
S = int(input())
if S > N:
    print(-1)
    exit()
if S == N:
    print(N + 1)
    exit()

for b in range(2, int(sqrt(N)) + 1):
    if f(b, N, S):
        print(b)
        exit()

for p in range(int(sqrt(N)), 0, -1):
    if (N - S) % p == 0:
        b = (N - S) // p + 1
        q = N - p * b
        if b > p >= 0 and b > q >= 0 and p + q == S:
            print(b)
            exit()

print(-1)

Solution (Python):

"""
Writer: SPD_9X2
https://atcoder.jp/contests/abc044/tasks/arc060_b

f(b,n)ってbが大きくなるほど大きくなる？(単調増加になる?)
→そんなことはない
nより大きかったら不可能。最小はn進法で桁和1

3桁以上になる物は全探索する
2桁は、良い感じにすべて調べ上げる
実装だるそ～

2桁の時 xyとなるとする
n//b = x
n%b  = y

n = bx+y
x+y = s

(n-S)//x+1 = b
かつ S >= x >= S-b

xについてn-sの約数を全列挙して、bを求める & 下の条件を満たしているか確認すればよい？
上の条件を満たしているbが必ずしも元の条件を満たすわけではなさそう？
ちゃんと満たしているか確認してあげる
"""

def f(b,n):

    if n < b:
        return n
    else:
        return f(b,n//b) + (n%b)

import sys
n = int(input())
s = int(input())

if s > n:
    print (-1)
    sys.exit()
elif s == n:
    print (n+1)
    sys.exit()

for b in range(2,int(n**0.5+10)):

    if f(b,n) == s:
        print (b)
        sys.exit()


ans = float("inf")

for x1 in range(1,10**6):

    if (n-s) % x1 == 0:

        x2 = (n-s)//x1

        b1 = (n-s)//x1+1
        if b1 ** 2 > n and s >= x1 >= s-b1 and f(b1,n) == s:
            ans = min(ans , b1)

        b2 = (n-s)//x2+1
        if b2 **2 > n and s >= x2 >= s-b2 and f(b2,n) == s:
            ans = min(ans , b2)

if ans == float("inf"):
    print (-1)
else:
    print (ans)

Solution (Python):


def f(mike, nim):
  return nim % mike + f(mike, nim // mike) if nim > 0 else 0

nim = int(input())
s = int(input())

for i in range(2, 5**8):
  if f(i, nim) == s:
    print(i)
    exit()

for i in range(nim - s >> 18, 0, -1):
  if f((nim - s) // i + 1, nim) == s:
    print((nim - s) // i + 1)
    exit()

print(nim + 1 if nim == s else -1)

Solution (Python):
N = int(input())
S = int(input())

def f(b, n):
    if n < b:
        return n
    else:
        return f(b, n//b) + (n % b)

def solve(N, S):
    if S > N:
        return -1
    elif N == S:
        return N+1
    else:
        for b in range(2, int(N**(1/2))+1):
            if f(b, N) == S:
                return b
        for p in range(int(N**(1/2)), 0, -1):
            if (N - S) % p == 0:
                b = (N - S) // p + 1
                if f(b, N) == S:
                    return b
        return -1

print(solve(N, S))

Solution (Python):
import math

n = int(input())
s = int(input())

b = -1

def keisan(k, w):
  l = []
  while k >= w:
    l.append(k % w)
    k = k // w
  else:
    l.append(k)
  return (sum(l))

if n == s:
  b = n + 1
  print(b)
  exit()
  
if n < s:
  b = -1
  print(b)
  exit()

n_r = math.floor(math.sqrt(n))

for i in range(2, n_r+1):
  if keisan(n, i) == s:
    b = i
    print(b)
    exit()

b_list = []    
    
for i in range(1, n_r+1):
  w = n - s
  syou = w // i
  amari = w % i
  if amari == 0:
    b_kouho = syou + 1
    b_list.append(b_kouho)


b_kansei = []

for b in b_list:
  b_ = keisan(n, b)
  if b_ == s:
    b_kansei.append(b)


if b_kansei != []:
  print(min(b_kansei))
else:
  print(-1)

Solution (Python):
import math

def func(b,n):
  if b > n:
    return n
  else:
    return func(b, math.floor(n/b)) + (n % b)

def _func(b,n):
  x = n
  ret = 0
  while True:
    if b > x:
      return ret + x
    else:
      ret += x % b
      x = math.floor(x/b)

def solve(n,s):
  if n == s:
    return n+1
  ans = float('inf')
  for b in range(2,math.floor(math.sqrt(n))+1):
    if _func(b,n) == s:
      return b

  for p in range(1,math.floor(math.sqrt(n))+1):
    if (n-s) % p == 0:
      b = int((n-s)/p)+1
      if b < 2:
        continue
      if _func(b, n) == s:
        ans = min(ans, b)

  if ans < float('inf'):
    return ans
  else:
    return -1

if __name__  == "__main__":
  n = int(input())
  s = int(input())
  ans = solve(n,s)
  print(ans)

Solution (Python):
n=int(input())
s=int(input())
if s==n:
  print(n+1)
  exit()
def f(x):
  m=n
  t=0
  while m:
    t+=m%x
    m//=x
  return t
for b in range(2,int(n**0.5)+2):
  if f(b)==s:
    print(b)
    exit()
for p in range(1,int(n**0.5))[::-1]:
  q=s-p
  b=(n-s)//p+1
  if 1<=p<b and 0<=q<b and (n-s)%p==0:
    b=(n-s)//p+1
    if f(b)==s:
      print(b)
      exit()
print(-1)

Solution (Python):
n = int(input())
s = int(input())

if n == s:
  print(n+1)
  exit(0)

m = int((n-1)**.5) + 2
for i in range(2, m):
  t = 0
  f = n
  while f:
    t += f % i
    f //= i
  if t == s:
    print(i)
    exit(0)

a = 10**12
for i in range(1, min(m, s+1)):
  j = s - i
  if (n - j) % i == 0:
    b = (n - j) // i
    if j < b and i < b:
      a = min(a, b)
print(a if a < 10**12 else -1)

Solution (Python):

import sys
input = sys.stdin.readline




def f(b,n):
    if n < b:
        return n
    else:
        return f(b, n//b) + n%b





N = int(input())
S = int(input())

ans = -1
if S==N:
    ans = N+1
else:
    
    for b in range(2, int(N**.5)+1):
        if f(b,N)==S:
            ans = b
            break


if ans == -1:
    
    
    
    for p in range(int(N**.5)+1,0,-1):
        b = (N-S)//p + 1
        
        if b >= 2 and f(b,N)==S:
            ans = b
            break

print(ans)

Solution (Python):
import math

def f(b, n):
    if n < b:
        return n
    return f(b, n // b) + (n % b)

"""
kari1 = 87654
kari2 = 30          
kari1 = 87654
kari2 = 138         
kari1 = 87654
kari2 = 45678       
kari1 = 31415926535
kari2 = 1           
kari1 = 1
kari2 = 31415926535 
n = int(kari1)
s = int(kari2)
"""
n = int(input())
s = int(input())

if n < s:
    print(-1)
elif n == s:
    print(n + 1)
else:
    b = 2
    while b * b <= n:
        if s == f(b, n):
            is_b = True
            break
        b += 1
    if b * b <= n:
        print(b)
    else:
        p = 1
        ans = -1
        while p * p <= n:
              if (n - s) % p != 0:
                    p += 1
                    continue
              else:
                    b = (n - s) // p + 1
                    if s == f(b, n):
                        ans = min(b, ans) if ans != -1 else b
              p += 1
        print(ans)

Solution (Python):
def D(n,d):
  r=0
  while n>0:
    r=r+n%d
    n=n//d
  return r

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

n=int(input())
s=int(input())
if n-s==0:
  print(n+1)
  exit()
if s>n:
  print(-1)
  exit()

A=make_divisors(n-s)
for i in range(len(A)):
  if D(n,A[i]+1)==s:
    print(A[i]+1)
    exit()
print(-1)

Solution (Python):
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    n=I()
    s=I()
    
    if s==n:
        print(n+1)
    elif s>n:
        print(-1)
    else:
        
        def calc(b,n):
            temp=0
            while n!=0:
                temp+=n%b
                n=n//b
            return temp
        
        ans=1000000000000
        N=1000000
        
        
        for b in range(2,N):
            if calc(b,n)==s:
                ans=b
                break
            
        if ans!=1000000000000:
            print(ans)
            
        
        else:
            
            for a1 in range(1,N):
                a0=s-a1
                if a0<0:
                    break
                if (n-a0)%a1==0:
                    b=(n-a0)//a1
                    if b>1000000 and a0<b and a1<b:
                        ans=min(ans,b)
                        
            if ans!=1000000000000:
                print(ans)
            else:
                print(-1)
        
        
    
    
    
    
    
    
            
    
        

main()

Solution (Python):
from math import floor, sqrt, ceil


def f(b, n):
    if n < b:
        return n

    return f(b, floor(n / b)) + n % b


n = int(input())
s = int(input())

if n == s:
    print(n + 1)
    exit()

for b in range(2, floor(sqrt(n)) + 1):
    if f(b, n) == s:
        print(b)
        exit()

for p in range(1, ceil(sqrt(n)))[::-1]:
    b = (n - s) / p + 1
    if b.is_integer():
        b = int(b)
        if 1 <= p < b and 0 <= s - p < b:
            print(b)
            exit()

print(-1)

Solution (Python):
from math import floor, sqrt, ceil


def f(b, n):
    if b < 2:
        return 0

    if n < b:
        return n

    return f(b, floor(n / b)) + n % b


n = int(input())
s = int(input())

if n == s:
    print(n + 1)
    exit()

for b in range(2, floor(sqrt(n)) + 1):
    if f(b, n) == s:
        print(b)
        exit()

for p in range(1, ceil(sqrt(n)))[::-1]:
    b = (n - s) / p + 1
    if b.is_integer():
        b = int(b)
        if 1 <= p < b and 0 <= s - p < b:
            print(b)
            exit()

print(-1)

Solution (Python):
from math import floor, sqrt, ceil


def f(b, n):
    if b < 2:
        return 0

    if n < b:
        return n

    return f(b, floor(n / b)) + n % b


n = int(input())
s = int(input())

if n == s:
    print(n + 1)
    exit()

for b in range(2, floor(sqrt(n)) + 1):
    if f(b, n) == s:
        print(b)
        exit()

for p in range(1, ceil(sqrt(n)))[::-1]:
    b = (n - s) / p + 1
    if b.is_integer():
        b = int(b)
        if f(b, n) == s:
            print(b)
            exit()

print(-1)

Solution (Python):
import math
import sys

n = int(input())
s = int(input())

up = math.sqrt(n)

def colsum(num, base):
    if num < base:
        return num
    else:
        return num%base + colsum(num//base,base)


if s == n:
    print(n+1)
elif s > n:
    print(-1)
else:
    
    for i in range(2,int(up)+1):
        if colsum(n,i) == s:
            print(i)
            sys.exit()

    
    for j in range(int(up),0,-1):
        if (n-s)%j == 0:
            b = (n-s)/j + 1
            if colsum(n,b) == s and b > 1:
                print(int(b))
                sys.exit()

    print(-1)

Solution (Python):
n = int(input())
s = int(input())
x = int(n**0.5)+1
def dsum(x,t):
  ret = 0
  while x>0:
    ret += x%t
    x //= t
  return ret
for i in range(2,x+1):
  if dsum(n,i) == s:
    print(i)
    exit()
for i in range(x,0,-1):
  if (n-(s-i))%i == 0:
    digit = (n-(s-i))//i
    if 0 < i < digit and 0 <= s-i < digit:
      print((n-(s-i))//i)
      exit()
if n == s:
  print(n+1)
  exit()
print(-1)

Solution (Python):

import sys


def f(b: int, n: int) -> int:
    if n < b:
        return n
    return f(b, n // b) + n % b


def sqrt(n: int):
    lb = 0
    hb = n + 1
    while hb - lb > 1:
        m = (lb + hb) // 2
        if m * m <= n:
            lb = m
        else:
            hb = m
    return lb


def solve(n: int, s: int):
    if s == n:
        print(n + 1)
        return
    sn = sqrt(n)
    for b in range(2, sn + 1):
        if f(b, n) == s:
            print(b)
            return
    for p in reversed(range(1, sn + 1)):
        q = s - p
        if q < 0:
            continue
        b, r = divmod(n - q, p)
        if r != 0 or b <= p:
            continue
        if f(b, n) == s:
            print(b)
            return
    print(-1)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  
    s = int(next(tokens))  
    solve(n, s)


if __name__ == '__main__':
    main()