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



Sample input:
87654
30


Sample output:
10

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
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

#A

#B

#C
"""
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)
"""

#D
sys.setrecursionlimit(1000000)
def f(b,n):
    if n<b:
        return n
    else:
        return n%b+f(b,n//b)
n,s = IR(2)
if n == s:
    print(n+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):
    if (n-s)%p == 0:
        b = (n-s+p)//p
        if f(b,n) == s:
            print(b)
            quit()
print(-1)

#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
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

#A

#B

#C
"""
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)
"""

#D
def f(b,n):
    if n<b:
        return n
    else:
        return n%b+f(b,n//b)
n,s = IR(2)
if n == s:
    print(n+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):
    if not (n-s)%p:
        b = (n-s+p)//p
        if f(b,n) == s:
            print(b)
            quit()
print(-1)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Runtime Error

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

memo = [[False for _ in range(n)] for _ in range(n)]

def f(x,y):
    print(memo[x][y])
    if memo[x][y]:
        return memo[x][y]
    elif y < x:
        memo[x][y] = y
        return y
    else:
        memo[x][y] = f(x, y//x)+(y%x)
        return memo[x][y]

# f()
for i in reversed(range(n)):
    print(f(i, n))
    if f(i, n) == s:
        print(b)
        exit()

print(-1)

Submission status: Runtime Error

Solution code:
#ABC044D
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
    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))

Submission status: Runtime Error

Solution code:
#ABC044D
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 s==1:return n
    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))

Submission status: Runtime Error

Solution code:
#ABC044D
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 s==1:return n
    for b in range(2,1+int(n_root//1)):
        if fun(b,n)==s:
            return b
    for i in range(1+int(n_root//1),0,-1):
        b=1+(n-s)//i
        if fun(b,n)==s:
            if b<=n_root or b<=1:continue
            if n//b>=b or n//b<1:continue
            return b
    return -1
print(main(n,n_root,s))

Submission status: Runtime Error

Solution code:
N,A = map(int,input().split())
X = [int(e) for e in input().split()]
# dp[i][k][s]: i番目まで見てk個選んで総和sとなる場合の数
# 初期条件: dp[0][0][0] = 1
# 遷移: dp[i][k][s] += dp[i-1][k-1][s-X[i]] + dp[i-1][k][s]
# 答え: sum(dp[N][k][k*A] 1 <= k <= N)
s_max = 2500
dp = [[[0]*(s_max+1) for k in range(N+1)] for i in range(N+1)]
dp[0][0][0] = 1
for i in range(1,N+1):
    for k in range(N+1):
        for s in range(s_max+1):
            dp[i][k][s] += dp[i-1][k][s]
            if k != 0 and 0 <= s-X[i-1] <= s_max:
                dp[i][k][s] += dp[i-1][k-1][s-X[i-1]]
ans = 0
for k in range(1,N+1):
    s = k*A
    ans += dp[N][k][s]
print(ans)

Submission status: Runtime Error

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

flag = False
if 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)

Submission status: Runtime Error

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

flag = False
if 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:
    print(b)
    flag = True
    exit()

if flag == False:
  print(-1)

Submission status: Runtime Error

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

flag = False
if 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:
    print(b)
    flag = True
    exit()

if flag == False:
  print(-1)

Submission status: Runtime Error

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

flag = False

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:
    print(b)
    flag = True
    exit()

if flag == False:
  print(-1)

Submission status: Runtime Error

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

flag = False

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:
    print(b)
    flag = True
    break

if flag == False:
  print(-1)

Submission status: Runtime Error

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

flag = False

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(chk(b,n))
    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:
    print(b)
    flag = True
    break

if flag == False:
  print(-1)

Submission status: Runtime Error

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

flag = False

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
    break

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

if flag == False:
  print(-1)

Submission status: Runtime Error

Solution code:
import math
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)
elif n < s:
  print(-1)
else:
  is_exist = False
  for i in range(2, int(math.sqrt(n))+1):
    if f(i, n) == s:
      print(i)
      is_exist = True
      break
  if not is_exist:
    for i in range(1, int(math.sqrt(n))+1):
      b = int((n - s) / i) + 1
      if f(b, n) == s:
        print(b)
        is_exist = True
        break
    if not is_exist:
      print(-1)

Submission status: Runtime Error

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

# コーナーケース
if N == S:
    print(N + 1)
    exit()


# x進数
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])


# Bが小さいとき
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()

# Bが大きいときはpを全探索
for p in range(1, int(N ** 0.5) + 1):
    b = (N - S) // p + 1
    encoded_N = encode_x_base(N, b)
    d_sum = digit_sum(encoded_N)
    if d_sum == S:
        print(b)
        break
else:
    print(-1)

Submission status: Runtime Error

Solution code:
n=int(input())
s=int(input())
rootn=0
while rootn**2<=n:
    rootn+=1

    
def fun(b,n):
    b=int(b)
    n=int(n)
    if n<b:return n
    elif n>=b:
        return fun(b,n//b)+n%b
def main(n,s):
    if n==s:return n+1
    for b in range(2,rootn):
        if fun(b,n)==s:return int(b)
    
    for p in reversed(range(1,rootn)):
        b=1+(n-s)//p
        if fun(b,n)==s:return int(b)
        b=2+(n-s)//p
        if fun(b,n)==s:return int(b)
    return -1

x=main(n,s)
print(x)
#http://arc060.contest.atcoder.jp/data/arc/060/editorial.pdf

Submission status: Runtime Error

Solution code:
n=int(input())
s=int(input())
rootn=0
while rootn**2<=n:
    rootn+=1

    
def fun(b,n):
    if n<b:return n
    elif n>=b:
        return fun(b,n//b)+n%b
def main(n,s):
    if n==s:return n+1
    for b in range(2,rootn):
        if fun(b,n)==s:return int(b)
    
    for p in reversed(range(1,rootn)):
        b=1+(n-s)//p
        if fun(b,n)==s:return int(b)
        b=2+(n-s)//p
        if fun(b,n)==s:return int(b)
    return -1

x=main(n,s)
print(x)
#http://arc060.contest.atcoder.jp/data/arc/060/editorial.pdf

Submission status: Runtime Error

Solution code:
n=int(input())
s=int(input())
rootn=0
while rootn**2<=n:
    rootn+=1

    
def fun(b,n):
    if n<b:return n
    elif n>=b:
        return fun(b,n//b)+n%b
def main(n,s):
    if n==s:return n+1
    for b in range(2,rootn):
        if fun(b,n)==s:return int(b)
    
    for p in range(1,rootn):
        if (n-s)%p==0:
            b=1+(n-s)/p
            if fun(b,n)==s:return int(b)
    return -1

x=main(n,s)
print(x)
#http://arc060.contest.atcoder.jp/data/arc/060/editorial.pdf

Submission status: Runtime Error

Solution code:
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>0:
            if f(b,N)==S:
                ans = b
                break

print(ans)

Submission status: Runtime Error

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

print(ans)

Submission status: Runtime Error

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

print(ans)

Submission status: Runtime Error

Solution code:
import math as m
def f(b,n):
    ans = 0
    while n > 0:
        ans += n % b
        n = m.floor(n/b)
    return ans

n = int(input())
s = int(input())
if n == s:
    print(n+1)
else:
    found = False
    for b in range(2,m.floor(m.sqrt(n))+1):
        if f(b,n) == s:
            print(b)
            found = True
            break
    if found == False:
        for p in range(m.floor(m.sqrt(n)),0,-1):
            if (n-s) % p == 0:
                b = (n-s)//p + 1
                if f(b,n) == s:
                    print(b)
                    found = True
                    break
        if found == False:
            print(-1)

Submission status: Runtime Error

Solution code:
import math as m
def f(b,n):
    if b > n:
        return n
    else:
        return f(b,m.floor(n/b)) + (n % b)

n = int(input())
s = int(input())
if n == s:
    print(n+1)
else:
    found = False
    for b in range(2,m.floor(m.sqrt(n))+1):
        if f(b,n) == s:
            print(b)
            found = True
            break
    if found == False:
        for p in range(m.floor(m.sqrt(n)),0,-1):
            if (n-s) % p == 0:
                b = (n-s)//p + 1
                if f(b,n) == s:
                    print(b)
                    found = True
                    break
        if found == False:
            print(-1)

Submission status: Runtime Error

Solution code:
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(0,int(math.sqrt(N))):
	B = (N-S)/p + 1
	if(B==int(B) and f(int(B),N)==S):
		print(B)
		exit()


print(-1)

Submission status: Runtime Error

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


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


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)

Submission status: Runtime Error

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


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


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(1, int(N ** 0.5) + 1):
        if (N - S) % i == 0:
            b = (N - S) // i + 1
            if f(b, N) == S:
                num = b
                break

print(num)

Submission status: Runtime Error

Solution code:
rom 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)

Submission status: Runtime Error

Solution code:

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)
elif s == 1:
    def check(n,b):
        if n == 1:
            return b
        else:
            if n % b !=0 :
                return 0
            else:
                return check(n // b,b)
    for b in range(2,rtn):
        r = check(n,b)
        if r:
            print(r)
            exit()
    print(n)
else:
    x = n // s
    if s - (n //(x+1))  <= x:
        x = x + 1
    if 5 < n/(x -1) - n/x :
        for b in range(n//x, n//(x-1)):
            if f(b,n) == s:
                print(b)
                exit()
        for i in range(x-1,2,-1):
            for b in range(n//i + (n//x)//(n//i), n//i + (n//x)//(n//i)  + (2*n//x - n//(x+1))//(x-i)):
                if f(b,n) == s:
                    print(b)
                    exit()
    else:
        for b in range(2,(n//3)+3):
            if f(b,n) == s:
                print(b)
                exit()
    print(n-s+1)

Submission status: Runtime Error

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

def f(b,n) :
    r = 0
    i = 1
    while n:
        j = n % b
        r += j
        n = (n-j)//b
    return r


if n < s or (n // 2)+1 < s < n :
    print("-1")
elif (n//3) + 2 < s < n//2:
    print(n-s+1)
elif s == n:
    print(n+1)
elif s == 1:
    def check(n,b):
        while 1 < n :
            if n % b != 0:
                break
            n //= b
        if n == 1:
            return b
        return 0
    for b in range(2,int(n**0.5)+2):
        r = check(n,b)
        if r:
            print(r)
            exit()
    print(n)
else:

    x = n // s
    xd = n % s
    if s - xd < x:
        x = x + 1
    if 3 < n/(x -1) - n/x :
        for b in range(n//(x-1),(n//x)+1):
            if f(b,n) == s:
                print(b)
                exit()
    for b in range(2,(n//2)+2):
        if f(b,n) == s:
            print(b)
            exit()
    print(n-s+1)

Submission status: Runtime Error

Solution code:
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(-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(t)) + 5):
        if t % i == 0:
            bs.add(i)
            bs.add(t // i)
    bs.add(N)
    bs.add(N + 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()

Submission status: Runtime Error

Solution code:
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)
else:
    for b in range(2, math.ceil(math.sqrt(n)) + 1):
        if f(b, n) == s:
            print(b)
            break
    else:
        for p in range(1, math.ceil(math.sqrt(n)) + 1):
            if s - p >= 0 and n-s+p > 0:
                b = round((n-s+p)/p, )
                if f(b, n) == s:
                    print(b)
                    break
        else:
            print(-1)

Submission status: Runtime Error

Solution code:
import math
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)
elif n < s:
    print(-1)
else:
    for b in range(2, int(math.sqrt(n)) + 1):
        if f(b, n) == s:
            print(b)
            break
    else:
        for p in range(1, int(math.sqrt(n)) + 1):
            b = int(((n-s)/p) + 1)
            if f(b, n) == s:
                print(b)
                break
        else:
            print(-1)

Submission status: Runtime Error

Solution code:
import math
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)
elif n == 1:
    print(-1)
else:
    for b in range(2, int(math.sqrt(n)) + 1):
        if f(b, n) == s:
            print(b)
            break
    else:
        for p in range(1, int(math.sqrt(n)) + 1):
            b = int(((n-s)/p) + 1)
            if f(b, n) == s:
                print(b)
                break
        else:
            print(-1)

Submission status: Runtime Error

Solution code:
import math
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)
elif n == 1:
    print(1 if s == 1 else -1)
else:
    for b in range(2, int(math.sqrt(n)) + 1):
        if f(b, n) == s:
            print(b)
            break
    else:
        for p in range(1, int(math.sqrt(n)) + 1):
            b = int(((n-s)/p) + 1)
            if f(b, n) == s:
                print(b)
                break
        else:
            print(-1)

Submission status: Runtime Error

Solution code:
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 = []
  while b:
    a.append(b%i)
    b//=i
  kota = sum(a)
  if s == kota:
    print(i)
    exit()
for i in range(ru,0,-1):
  q = s-i
  if q <0:
    continue
  c = (n-q)// i
  b = n+0
  a = []
  while b:
    a.append(b%c)
    b//=c
  kota = sum(a)
  if kota == s:
    print(c)
    exit()
print(-1)

Submission status: Runtime Error

Solution code:

# -*- coding: utf-8 -*-
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

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

    return -1


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

    print(slv(N, S))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

def f(bi,nu):
    if nu<bi:
        return nu
    else:
        return f(bi,nu//bi)+nu%bi
    
if s==n:
    ans=n+1
elif n<s:
    ans=-1
else:
    for i in range(2,int(n**0.5)+1):
        if f(i,n)==s:
            ans=i
            break
    else:
        for i in range(int(n**0.5),0,-1):
            b=int((n-s)/i)+1
            if f(b,n)==s:
                ans=b
print(ans)

Submission status: Runtime Error

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

def f(bi,nu):
    if nu<bi:
        return nu
    else:
        return f(bi,nu//bi)+nu%bi
    
if s==n:
    ans=n+1
elif n<s:
    ans=-1
else:
    for i in range(2,int(n**0.5)+1):
        if f(i,n)==s:
            ans=i
            break
    else:
        for i in range(1,int(n**0.5)+1):
            b=int((n-s)/i)+1
            if f(b,n)==s:
                ans=b
print(ans)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
from math import sqrt
n = int(input())
s = int(input())
def f(x,y):
	if y<x: return y
	else: return f(x,y//x)+(y%x)
if s==n: ans = n+1
else:
	ans = -1
	for i in range(2,int(sqrt(n))+1):
		if f(i,n)==s:
			ans = i
			break
	if ans==-1:
		for i in range(int(sqrt(n)),0,-1):
			b = (n-s)/i+1
			if b==int(b) and f(int(b),n)==s:
				ans = int(b)
				break
print(ans)

Submission status: Runtime Error

Solution code:
import math

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

ans = []

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

if n == s:
  ans.append(n+1)

elif s == 1:
  ans.append(n)
  
else:
  rootn = int(math.sqrt(n))
  for b in range(2, rootn):
    if s == f(b, n):
      ans.append(b)
      break
      
  for p in range(1, rootn):
    b = (n-s)//p + 1
    if s == p*b + n%b:
      ans.append(b)
      
if not ans:
  ans.append(-1)

print(min(ans))

Submission status: Runtime Error

Solution code:
import math

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

ans = -1

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

if n == s:
  ans = n+1

elif s == 1:
  ans = n
  
else:
  rootn = int(math.sqrt(n))
  for b in range(2, rootn):
    if s == f(b, n):
      ans = b
      break
  else:
    for p in range(1, rootn):
      b = (n-s)//p + 1
      if s == p*b + n%b:
        ans = b
        break

print(ans)

Submission status: Runtime Error

Solution code:
import math

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

ans = -1

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

if n == s:
  ans = n+1
  
else:
  rootn = int(math.sqrt(n))
  for b in range(2, rootn):
    if s == f(b, n):
      ans = b
      break
  else:
    for p in range(1, rootn):
      b = (n-s)//p + 1
      if s == p*b + n%b:
        ans = b
        break

print(ans)

Submission status: Runtime Error

Solution code:
import math

n = int(input())
s = int(input())
f = None
for i in range(2, math.ceil(math.sqrt(n))):
    c = 0
    k = n
    while k > 0:
        c += k % i
        k //= i
    if c == s:
        f = i
        break
if f is None:
    for i in range(int(math.sqrt(n)), 1, -1):
        b = n // i
        k = b
        while k > 0:
            c += k % b
            k //= b
        if (s - c) % i == 0 and b + (s - c) // i < n // (i + 1):
            print(i, b, c, s - c)
            f = b + (s - c) // i
            break
if f is None and s <= n // 2:
    f = n - s + 1
if f is None: print(-1)
else: print(f)

Submission status: Runtime Error

Solution code:
import math
n=input()
s=input()

def f(b,n):
	if n<b:
		return n
	elif n>=b:
		return f(b, math.floor(n/b))+n%b

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


# 2 <= b <= sqrt(n)
n_sqrt=int(math.sqrt(n))
for i in range(2, n_sqrt+1):
	if f(i,n)==s:
		print i
		quit()



# sqrt(n) < b <= n
# yakusuu
l=[]
for i in range(1, n_sqrt+1):
	if (n-s)%i==0:
		l.append(i)
		l.append((n-s)/i)


for i in l:
	b=i+1
	p=n/b
	q=n%b
	if p+q==s:
		print b
		quit()

print -1

Submission status: Runtime Error

Solution code:
import math
n=input()
s=input()

def f(b,n):
	if n<b:
		return n
	elif n>=b:
		return f(b, math.floor(n/b))+n%b

if s==1:
	print n
	quit()
if n==1:
	print -1
	quit()



for i in range(2,s+1):
	if f(i,n)==s:
		print i
		quit()
else:
	print -1