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 collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    n = II()
    k = II()
    x = II()
    y = II()
    ans = 0
    for i in range(n):
        if i >= k:
            ans += y
        else:
            ans += x
    print(ans)
    return


def B():
    w = S()
    d = defaultdict(int)
    for s in w:
        d[s] += 1
    for di in d.values():
        if di % 2:
            print("No")
            return
    print("Yes")
    return


def C():
    n, a = LI()
    x = LI()
    sumx = [0] * n
    for i in range(n):
        sumx[i] = sumx[i - 1] + x[i]
    dp = [[[0] * (n+1) for i in range(sumx[-1] + 1)] for i in range(n)]
    for i in range(n):
        dp[i][x[i]][1] = 1
    for i in range(1, n):
        for s in range(sumx[i] + 1):
            for k in range(1, i + 2):
                if  s >= x[i]:
                    dp[i][s][k] += dp[i - 1][s - x[i]][k - 1]
                dp[i][s][k] += dp[i - 1][s][k]
    ans = 0
    for i in range(1, n + 1):
        if a * i > sumx[-1]:
            break
        ans += dp[-1][a * i][i]
    print(ans)
    return












def D():
    def f(b, n):
        if n < b:
            return n
        return f(b, n // b) + (n % b)
    n, s = IR(2)
    if n == s:
        print(n + 1)
        return
    for b in range(2, int(math.sqrt(n)) + 1):
        if s == f(b, n):
            print(b)
            return
    for p in range(int(math.sqrt(n)), 0, -1):
        b = (n - s) // p + 1
        if b <= 1:
            continue
        if s == f(b, n):
            print(b)
            return
    print(-1)
    return



if __name__ == '__main__':
    D()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

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

n,s = [int(input()) for _ in [0]*2]
b = -1
if n==s:b=n+1
else:
    for i in range(2,int(n**0.5)+1):
        if f(i,n)==s:
            b = i
            break
    else:
        for i in range(int(n**0.5),0,-1):
            j = (n-s)//i + 1
            if f(j,n)==s:
                b = j
                break
print(b)

Solution (Python):

import sys


def check(num, s, b):
    sum_keta = 0
    while num > 0:
        sum_keta += num % b
        num //= b
    if sum_keta == s:
        return 1
    else:
        return 0


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

    if num < s:
        print(-1)
        sys.exit()

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

    if num == 1:
        print(-1)
        sys.exit()

    for b in range(2, int(num ** 0.5) + 2):
        if check(num, s, b):
            print(b)
            sys.exit()

    for p in range(1, int(num ** 0.5) + 2)[::-1]:
        b = (num - s) // p + 1
        if b <= 1:
            continue
        if check(num, s, b):
            print(b)
            sys.exit()

    print(-1)






if __name__ == '__main__':
    main()

Solution (Python):
from math import ceil
from itertools import permutations



from heapq import *
"""
import sys
input=sys.stdin.readline
"""
from collections import defaultdict
from fractions import gcd

from math import sqrt
import sys
sys.setrecursionlimit(100100)

from collections import deque
import bisect
import sys
input=sys.stdin.readline

n=int(input())
s=int(input())
if s>n:
    print(-1)
    quit()
if s==n :
    print(n+1)
    quit()
def func(b,n):
    res=0
    while(n):
        res+=n%b
        n//=b
    return res
j=1
i=n
ans=10**30
for i in range(2,int(sqrt(n))+1):
    if func(i,n)==s:
        ans=min(ans,i)
l=defaultdict()
for i in range(1,ceil(sqrt(n))):
    b=(n-s)//i+1
    if sqrt(n)<b and n//b+(n%b)==s:
        ans=min(ans,b)
if ans==10**30:
    print(-1)
else:
    print(ans)

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

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

def solve(n, s) :
    if n == s :
        return n + 1
    if s > n :
        return -1
    
    b = 2
    while b * b <= n :
        if f(b, n) == s :
            return b
        b += 1
            
    p = int(-(-(n ** 0.5 - 1) // 1))
    while p > 0 :
        if (n - s) % p == 0 :
            b = 1 + (n - s) // p
            if p < b and 0 <= s - p < b :
                return b
            
        p -= 1
        
    return -1
            
print(solve(n, s))

Solution (Python):
import math
import os
import sys
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, S = [int(sys.stdin.readline()) for _ in range(2)]


@lru_cache(maxsize=None)
def f(b, n):
    if n < b:
        return n
    return f(b, int(n // b)) + n % b


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












b = 2
ans = -1
while b <= math.sqrt(N) + 1:
    if f(b, N) == S:
        ans = b
        break
    b += 1
if ans >= 0:
    print(ans)
    exit()

ans = INF

for d2 in range(1, int(math.sqrt(N)) + 1):
    if (N - S) % d2 == 0:
        b = int(1 + (N - S) // d2)
        if b >= 2 and f(b, N) == S:
            ans = min(ans, b)
if ans == INF:
    print(-1)
else:
    print(ans)

Solution (Python):
import math
import sys
sys.setrecursionlimit(10**5)
n = int(input())
s = int(input())

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

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

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

if n == 1:
    print (-1)
    exit()

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

for p in range(int(math.sqrt(n))+1, 0, -1):
    b = (n-s)//p + 1
    if b != 1 and f(b, n) == s:
        print (b)
        exit()
print (-1)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)

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

n=int(input())
s=int(input())
if s>n:
  print(-1)
elif s==n:
  print(n+1)
else:
  ans=10**18
  for i in range(2,int(n**0.5)+1):
    if f(i,n)==s:
      ans=i
      break
  if ans!=10**18:
    print(ans)
  else:
    for i in range(1,int(n**0.5)+1):
      tb=(n-s)//i+1
      if tb==1:
        continue
      if f(tb,n)==s:
        ans=min(ans,tb)
    if ans!=10**18:
      print(ans)
    else:
      print(-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


def solve(n,s):
  if s > n:
    return -1
  if s == n:
    return n+1
  nsq = int(n**0.5 + 1)
  for b in range(2,nsq+1):
    if f(b,n) == s:
      return b
  
  
  
  m = n-s
  msq = int(m**0.5+1)
  for x in range(msq,0,-1):
    if m%x:
      continue
    b = m//x+1
    if f(b,n) == s:
      return b
  return -1
  
answer = solve(n,s)
print(answer)

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

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

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

for k in range(2,math.floor(math.sqrt(n))+2):
    if f(k,n) == s:
        print(k)
        exit(0)

P = [1,n-s]
for k in range(2,math.floor(math.sqrt(n-s))+1):
    if (n-s) % k == 0:
        P.append(k)
        P.append((n-s)//k)

P = sorted([p+1 for p in P])
for b in P:
    if f(b,n) == s:
        print(b)
        exit(0)
print(-1)

Solution (Python):
import math


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


def main():
    n = int(input())
    s = int(input())
    if s == n:
        print(n+1)
        return
    elif s > n:
        print(-1)
        return
    sqrt = int(math.sqrt(n))
    for b in range(2, sqrt+2):
        if f(b, n) == s:
            print(b)
            return
    for x in range(sqrt, 0, -1):
        if x > s:
            continue
        y = s - x
        b = (n - y) // x
        if b >= 2 and (n - y) % x == 0 and f(b, n) == s:
            print(b)
            return
    print(-1)


if __name__ == "__main__":
    main()

Solution (Python):
def main():
	n = int(input())
	s = int(input())
	ans = solve(n, s)
	print(ans)

def solve(n: int, s: int) -> int:
	if n == s:
		return n+1

	def f(b:int, n:int) -> int:
		if b < 2:
			return -1
		if b > n:
			return n
		cur = n
		ans = 0
		while cur > 0:
			ans += cur%b
			cur //= b
		return ans

	sqrtn = int(n**0.5)
	for i in range(2, sqrtn):
		this_ans = f(i, n)
		if this_ans == s:
			return i

	for p in range(sqrtn+1, 0, -1):
		if (n-s)%p != 0:
			continue
		b = (n-s)//p + 1
		if f(b, n) == s:
			return b
	return -1


if __name__ == '__main__':
	main()

Solution (Python):
import sys

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

    if b > n:
        return n

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


def main():
    input = sys.stdin.readline
    n = int(input())
    s = int(input())

    if s > n:
        return -1

    if s == n:
        return n+1

    for i in range(2, int(n**0.5)):
        if f(i, n) == s:
            return i

    for p in range(int(n**0.5) + 1, 0, -1):
        if (n - s) % p != 0:
            continue

        b = (n - s) // p + 1
        if f(b, n) == s:
            return b

    return -1


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

Solution (Python):
import math


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


def digit_sum(n: int, s: int) -> int:
    if n == s:
        return n + 1

    sqrt = math.sqrt(n)
    sqrt = math.ceil(sqrt)

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

    for p in range(sqrt, 0, -1):
        if (n - s) % p:
            continue

        b = (n - s) // p + 1

        if b < 2:
            continue

        if f(b, n) == s:
            return b

    return -1


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

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

n = int(input().rstrip())
s = int(input().rstrip())

def f(b, n):
	if n < b:
		return n
	else:
		return f(b, int(n/b)) + (n % b)
if s == n:
	print(n+1)
else:
	for i in range(2, int(n**(1/2))+1):
		if f(i, n) == s:
			print(i)
			break
	else:
		for p in range(int(n**(1/2)), 0, -1):
			if (n-s) % p == 0:
				b = (n-s)/p + 1
				if b >= 2 and f(b, n) == s:
					print(int(b))
					break
			else:
				continue
		else:
			print(-1)

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

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

ans=-1
if s==n:
	ans=n+1
else:
	for _b in range(2,int(n**0.5)+1):
		if f(_b,n)==s:
			ans=_b
			break
	if ans==-1:
		for _p in range(int(n**0.5),0,-1):
			_b = (n-s)//_p+1
			if f(_b,n)==s:
				ans=_b
				break
print(ans)

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

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

m = int(n ** 0.5) + 1

for b in range(2, m + 1):
    temp = n
    t = 0
    while temp >= b:
        t += temp % b
        temp //= b
    if s == t + temp:
        print(b)
        exit()

for p in range(m, 0, -1):
    if (n - s) % p != 0:
        continue
    b = (n - s) // p + 1
    temp = n
    t = 0
    while temp >= b:
        t += temp % b
        temp //= b
    if s == t + temp:
        print(b)
        exit()

print(-1)

Solution (Python):

from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007






"""
n,a = LI()
x = LI()
s = sum(x)
dp = [[[0 for i in range(s+1)] for j in range(n+1)] for k in range(n+1)]
for i in range(n+1):
    dp[i][0][0] = 1
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(s+1):
            if k >= x[i-1]:
                dp[i][j][k] = dp[i-1][j][k]+dp[i-1][j-1][k-x[i-1]]
            else:
                dp[i][j][k] = dp[i-1][j][k]
ans = 0
for i in range(1,n+1):
    if a*i <= s:
        ans += dp[n][i][a*i]
print(ans)
"""


def f(b,n):
    m = n
    res = 0
    while m > 0:
        res += m%b
        m //= b
    return res
n,s = IR(2)
if n == s:
    print(n+1)
    quit()
if n == 1:
    print(-1)
    quit()
k = int(n**0.5)
for b in range(2,k+1):
    if f(b,n) == s:
        print(b)
        quit()
for p in range(1,k+1)[::-1]:
    if (n-s)%p == 0:
        b = (n-s)//p+1
        if b != 0:
            if f(b,n) == s:
                print(b)
                quit()
print(-1)

Solution (Python):

def fun(b,n):
    if b<2:return -1
    if n<b:return n
    return (n%b)+fun(b,n//b)
n=int(input())
s=int(input())
n_root=n**0.5

def main(n,n_root,s):
    if s==n:return n+1
    if s>n:return -1
    for b in range(2,1+int(n_root)):
        if fun(b,n)==s:
            return b
    for i in range(int(n_root),0,-1):
        b=1+(n-s)//i
        if fun(b,n)==s:
            if b>1:return b
    return -1
print(main(n,n_root,s))

Solution (Python):

def fun(b,n):
    if n<b:return n
    return (n%b)+fun(b,n//b)
n=int(input())
s=int(input())
n_root=n**0.5

def main(n,n_root,s):
    if s==n:return n+1
    if s>n:return -1
    if (n//2)+1<s:return -1
    for b in range(2,1+int(n_root)):
        if fun(b,n)==s:
            return b
    for i in range(int(n_root),0,-1):
        b=1+(n-s)//i
        if fun(b,n)==s:
            if b>1:return b
    return -1
print(main(n,n_root,s))

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

flag = False
if s > n or (n//2)+1<s<n:
  print(-1)
  exit()
  
if s == n:
  print(n+1)
  exit()

def chk(b, n):
  if n//b == 0:
    return n
  else:
    return chk(b,n//b) + n%b

for b in range(2, int(n**0.5)+1):
  if chk(b, n) == s:
    print(b)
    flag = True
    exit()

for i in range(int(n**0.5), 0, -1):
  b = (n-s)//i + 1
  if chk(b, n) == s:
    if b > 1:
      print(b)
      flag = True
      exit()

if flag == False:
  print(-1)

Solution (Python):


"""
・参考：http://arc060.contest.atcoder.jp/data/arc/060/editorial.pdf
　　　　https://www.youtube.com/watch?v=LzxPxJ-cSHk
・b <= √nは愚直に当たっていく。
・b > √nは、b^2 > nなので、b進数で2桁以下になる。
　例) 10^2は10進数で100、100 > n → nは99以下
　その2桁の数字はn = p*b + qと表せる。
　例) 67 = 6*10 + 7
　今回の問題の条件から、s = p + q
　n = p*b + q
　s = p + q
　上記2つの式から、連立方程式でqを消すと、
　n-s = p*b - p
　と表せる。
　pはb以上なら桁が上がってしまうので p < b
　p < b から p*p < p*b なので、p*b > p^2
　よって、n = p*b + q >= p*b > p^2
　n > p^2 なので、√n > p
　つまりpについて√nまでを全探索すればOK。
　n-s = p*b - p をbについての形に変形すればbが出せる。
　b = (n-s)/p + 1
"""

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

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

n = INT()
s = INT()

if s > n:
    print(-1)
elif s == n:
    print(n+1)
elif ceil(n/2) < s < n:
    print(-1)
else:
    
    for b in range(2, int(sqrt(n))+2):
        if f(b, n) == s:
            print(b)
            exit()
    
    
    for p in range(int(sqrt(n))+2, 0, -1):
        
        if (n-s)%p: continue
        b = (n-s)//p + 1
        if f(b, n) == s:
            print(b)
            exit()
    
    print(-1)

Solution (Python):
def f(b, n):
  return n % b + f(b, n // b) if n > 0 else 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()
print(n + 1 if n == s else -1)

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


if N == S:
    print(N + 1)
    exit()



def encode_x_base(n, x):
    ret = []
    while n:
        ret.append(n % x)
        n //= x
    return ret[::-1]



def digit_sum(n):
    if isinstance(n, (int, str)):
        return sum([int(d) for d in str(n)])
    if isinstance(n, list):
        return sum([int(d) for d in n])



for b in range(2, int(N ** 0.5) + 1):
    encoded_N = encode_x_base(N, b)
    d_sum = digit_sum(encoded_N)
    if d_sum == S:
        print(b)
        exit()


for p in range(int(N ** 0.5) + 1, 0, -1):
    b = (N - S) // p + 1
    if b < 2:
        continue
    encoded_N = encode_x_base(N, b)
    d_sum = digit_sum(encoded_N)
    if d_sum == S:
        print(b)
        break
else:
    print(-1)

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

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

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 i in range(int(N**.5)+1,0,-1):
        b = (N-S)//i + 1
        if b>1:
            if f(b,N)==S:
                ans = b
                break

print(ans)

Solution (Python):
import math

def digitsum(x, b):
    accum = 0
    while x > 0:
        accum += x % b
        x //= b
    return accum

def solve(n, s, max_ns):
    if n < s: return -1
    
    max_digits = int(math.ceil(math.log2(max_ns)))
    
    min_b = n + 2

    
    if n == s:
         min_b = n + 1

    
    
    
    
    
    
    for q in range(1, int((n - s)**0.5) + 1):
        if (n - s) % q == 0:
            for b in [q + 1, (n - s) // q + 1]:
                if b < min_b:
                    if digitsum(n, b) == s:
                        min_b = b

    
    
    
    b_low = 2
    b_high = min(min_b, int(n ** 0.5) + 1)
    for b in range(b_low, b_high):
        if digitsum(n, b) == s:
            min_b = b

    if min_b < n + 2:
        return min_b
    return -1

def test():
    import random
    random.seed(0)
    for i in range(100):
        b = random.randint(2, 10**11)
        n = random.randint(1, 10**11)
        s = digitsum(n, b)
        solved_b = solve(n, s, 10**11)
        if s == digitsum(n, solved_b) and solved_b <= b:
            print('OK b={}, n={}, s={}, solved_b={}'.format(b, n, s, solved_b))
        else:
            print('NG!!! b={}, n={}, s={}, solved_b={}'.format(b, n, s, solved_b))

if __name__ == '__main__':
    n = int(input())
    s = int(input())
    print(solve(n, s, 10**11))

Solution (Python):

from math import sqrt
n, s = map(int, open(0).read().split())


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

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


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


for p in range(int(sqrt(n)), 0, -1):
    if (n - s) % p > 0:
        continue
    b = (n - s) // p + 1
    if b*b <= n:
        continue
    if f(b, n) == s:
        print(b)
        exit(0)
print(-1)

Solution (Python):
import math
n, s = [int(input()) for _ in range(2)]


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


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

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

for p in range(int(math.sqrt(n)) + 1, 0, -1):
    if (n - s) % p == 0:
        b = (n - s) // p + 1
        if b >= 2 and f(b, n) == s:
            print(b)
            exit()

print(-1)

Solution (Python):
import math
import sys

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

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

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

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

for i in range(int(math.sqrt(n)),0,-1):

    if s-i>=0 and n-(s-i)>=0 and (n-(s-i))%i==0 and (n-(s-i))//i>s-i:
        print((n-(s-i))//i)
        sys.exit()

print(-1)

Solution (Python):
import math

def gcd(a,b):
    """Compute the greatest common divisor of a and b"""
    while b > 0:
        a, b = b, a % b
    return a
 
def lcm(a, b):
    """Compute the lowest common multiple of a and b"""
    return a * b / gcd(a, b)
 

def f(b,n):
	if n < b:
		return n
	return f(b, n//b) + n%b
 
N = int(input())
S = int(input())

if N == S:
	print(N+1)
	exit()

if N < S:
	print(-1)
	exit()

for B in range(2, int(math.sqrt(N))+1):
	if(f(B,N)==S):
		print(B)
		exit()


for p in range(int(math.sqrt(N))+1, 0, -1):
	B = (N-S)/p + 1
	if(B==int(B) and f(int(B),N)==S):
		print(int(B))
		exit()


print(-1)

Solution (Python):
n = int(input())
s = int(input())
d = 0
k = 1
while k*k <= n-s:
  if (n-s)%k > 0:
    k += 1
    continue
  l = (n-s)//k
  if (l+1)*(l+1) > n:
    b = l+1
    if n//b + n%b == s:
      d = b
  b = k+1
  a = 0
  r = n
  while r > 0:
    a += r%b
    r = r//b
  if a == s:
    print(b)
    exit()
  k += 1
if n == s:
  print(n+1)
elif d>0:
  print(d)
else:
  print(-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


if N == S:
    print(N + 1)
    exit()
elif N < S:
    print(-1)
    exit()

num = -1
for i in range(2, int(N ** 0.5) + 1):
    if f(i, N) == S:
        num = i
        break


if num == -1:
    for i in range(int(N ** 0.5) + 1, 0, -1):
        if (N - S) % i == 0:
            b = (N - S) // i + 1
            if f(b, N) == S:
                num = b
                break

print(num)

Solution (Python):
def f(b, n):
    if n < b:
        return n
    elif n >= b:
        return f(b, n//b) + (n % b)

n, s = [int(input()) for _ in range(2)]
if s == n:
    ans = n+1
elif n < s:
    ans = -1
else:
    ans = -1
    for i in range(2, int(n**0.5)+1):
        if f(i, n) == s:
            ans = i
            break
    if ans == -1:
        for i in range(int(n**0.5), 0, -1):
            b = (n - s) / i + 1
            if b == int(b) and f(int(b), n) == s:
                ans = int(b)
                break
print(ans)

Solution (Python):
from math import floor,ceil
def f(b,n):
    if n < b:
        return n
    else:
        return f(b,floor(n/b))+n%b
n = int(input())
s = int(input())

for b in range(2,320000):
    if f(b,n)==s:
        print(b)
        exit()

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

d = {}
for i in range(1,ceil(n**0.5)):
    m = f(n//i,n)
    if n//i==n//(i+1):
        d[i] = (m,m)
    else:
        M = f(n//(i+1)+1,n)
        d[i] = (m,M)

for i in range(ceil(n**0.5)-1,0,-1):
    m,M = d[i]
    if m<=s<=M and (s-m)%i==0:
        print(n//i-(s-m)//i)
        exit()

print(-1)

Solution (Python):
n = int(input())
s = int(input())
rtn = -1* int( -1 * (n**0.5))
def f(b,n):
    if n<b:
        return n
    return f(b,n//b) + n % b
if n < s or (n // 2)+1 < s < n :
    print("-1")
elif s == n:
    print(n+1)
elif s == n//2 +1:
    if n % 2 == 1:
        print(n//2 + 1)
    else:
        print("-1")
elif (n//3) + 2 < s <= n//2:
    print(n-s+1)
else:
    for b in range(2,rtn+1):
        if f(b,n) == s:
            print(b)
            exit()
    for p in range(rtn,0,-1):
        if (n-s) % p == 0:
            b = (n-s)//p + 1
            if f(b,n) == s:
                print(b)
                exit()
    print(n-s+1)

Solution (Python):
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


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


def main():
    N = int(input())
    S = int(input())

    if N == S:
        print(N + 1)
        return
    if N < S:
        print(-1)
        return

    ans = INF
    for b in range(2, int(sqrt(N)) + 1):
        if f(b, N) == S:
            ans = min(ans, b)

    bs = set()
    t = N - S
    for i in range(1, int(sqrt(N)) + 1):
        if t % i == 0:
            bs.add(i + 1)
            bs.add((t // i) + 1)
    
    for b in bs:
        if b == 1:
            continue
        if f(b, N) == S:
            ans = min(ans, b)

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


if __name__ == '__main__':
    main()

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

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

if n == s:
    print(n+1)
elif n < s:
    print(-1)
else:
    limit = math.ceil(math.sqrt(n))
    for b in range(2, limit + 1):
        if f(b, n) == s:
            print(b)
            break
    else:
        for p in range(limit, 0 ,-1):
            if s - p >= 0 and n-s+p > 0 and (n-s+p)//p > limit:
                b = (n-s+p)//p
                if f(b, n) == s:
                    print(b)
                    break
        else:
            print(-1)

Solution (Python):
import math
n = int(input())
s = int(input())
if n == s:
  print(n+1)
  exit()
ru = math.ceil(math.sqrt(n))+1
for i in range(2,ru+1):
  b = n+0
  a = 0
  while b:
    a +=b%i
    b//=i
  if s == a:
    print(i)
    exit()
for i in range(ru,0,-1):
  q = s-i
  if q <0:
    continue
  c = (n-q)// i
  if c <= ru-1:
    continue
  b = n+0
  a = 0
  while b:
    a+=b%c
    b//=c
  if a == s:
    print(c)
    exit()
print(-1)

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

if N < S:
    print(-1)
    exit()
if N == S:
    print(N+1)
    exit()

rt = int(N**0.5)
for b in range(2,rt+1):
    a = 0
    n = N
    while n >= b:
        a += n%b
        n //= b
    a += n
    if a == S:
        print(b)
        exit()

d = N-S
divisors = set()
m = 1
while m*m <= d:
    if d%m == 0:
        divisors.add(m)
        divisors.add(d//m)
    m += 1

ans = INF = float('inf')

for p in divisors:
    if p > S: continue
    b = d // p + 1
    if b*b <= N: continue
    q = S - p
    if q >= b: continue
    ans = min(ans, b)

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

Solution (Python):
from math import sqrt

def n_based(n:int, base:int) -> int:
    if n == 0:
        return 0
    
    ans = 0
    res = n
    
    while abs(res) > 0:
        q = res%base
        if q>=0:
            ans = q + ans
            res //= base
        else:
            q += abs(base)
            ans = q + ans
            res //= base
            res += 1
        
    return ans


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

def judge(n:int, s:int) -> int:
    if n < s:
        return -1
    elif n==1 and s==1:
        return 2
    elif n == s:
        return n+1
    else:
        for i in range(2,int(sqrt(n))+2):
            
            if n_based(n,i) == s:
                return i
            
        for p in range(int(sqrt(n)), 0, -1):
            if (n-s+p) % p == 0:
                b = (n-s+p) // p
                
                if n_based(n,b) == s:
                    return b
                
                
        return -1
    
print(int(judge(n,s)))

Solution (Python):


import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


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


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, S):
    if S == N:
        return N + 1

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

    for b in range(2, int(math.sqrt(N)) + 1):
        s = f(b, N)
        if s == S:
            return b

    cnd = []
    for p in range(1, int(math.sqrt(N))+1):
        b = (N - S) // p + 1
        if b < 2:
            continue
        s = f(b, N)
        if s == S:
            cnd.append(b)

    if cnd:
        return min(cnd)

    return -1


def main():
    N = read_int()
    S = read_int()

    print(slv(N, S))


if __name__ == '__main__':
    main()