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:
import math


def f(n, base):
    X_dumy = base
    lis = []
    while X_dumy > 0:
        lis.append(X_dumy % n)
        X_dumy = int(X_dumy / n)
    return sum(lis)


def solve():
    N, S = int(input()), int(input())
    # print(N, S)

    if N == S:
        return N + 1

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

    largest = N**2
    lowest = largest
    for p in range(1, int(math.sqrt(N)) + 1):
        b = int((N - S) / p + 1)
        if f(b, N) == S:
            lowest = min(lowest, b)

    if not lowest == largest:
        return lowest

    return -1


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

Submission status: Runtime Error

Solution code:
import math


def f(base, n):
    # 10進数 n を, base 進数に変換して各桁を足し合わせる
    lis = []
    while n > 0:
        # print('除', n // base, 'あまり', n % base)
        lis.append(n % base)
        n = n // base
    return sum(lis)


def solve():
    N, S = int(input()), int(input())
    # print(N, S)
 
    if N == S:
        return N + 1
 
    for b in range(2, int(math.sqrt(N)) + 1):
        if f(b, N) == S:
            return b
 
    largest = N ** 2
    lowest = largest
    for p in range(1, int(math.sqrt(N)) + 1):
        buf = (N - S) / p
        if buf.is_integer():
            if f(buf + 1, N) == S:
                b = int(buf + 1)
                lowest = min(lowest, b)
 
    if not lowest == largest:
        return lowest
 
    return -1


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

Submission status: Runtime Error

Solution code:
import math

def f(base, n):
    # 10進数 n を, base 進数に変換して各桁を足し合わせる
    lis = []
    while n > 0:
        # print('除', n // base, 'あまり', n % base)
        lis.append(n % base)
        n = n // base
    return sum(lis)


def solve():
    N, S = int(input()), int(input())
    # print(N, S)
 
    if N == S:
        return N + 1
 
    for b in range(2, int(math.sqrt(N)) + 1):
        if f(b, N) == S:
            return b
 
    largest = N + 2
    lowest = largest
    for p in range(1, int(math.sqrt(N)) + 1):
        buf = (N - S) / p
        if buf.is_integer():
            if f(buf + 1, N) == S:
                b = int(buf + 1)
                lowest = min(lowest, b)
 
    if not lowest == largest:
        return lowest
 
    return -1


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

Submission status: Runtime Error

Solution code:
import math


def f(base, n):
    # 10進数 n を, base 進数に変換して各桁を足し合わせる
    lis = []
    while n > 0:
        # print('除', n // base, 'あまり', n % base)
        lis.append(n % base)
        n = n // base
    return sum(lis)


def solve():
    N, S = int(input()), int(input())
    # print(N, S)

    if N == S:
        return N + 1

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

    largest = N + 2
    lowest = largest
    for p in range(1, int(math.sqrt(N))):
        buf = (N - S) / p
        if buf.is_integer():
            if f(buf + 1, N) == S:
                b = int(buf + 1)
                lowest = min(lowest, b)

    if not lowest == largest:
        return lowest

    return -1


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

Submission status: Runtime Error

Solution code:
import math


def solve():
    N, S = int(input()), int(input())
    # print(N, S)
    
    floor = math.floor
    def f(b, n):
        if n < b:
            return n
        if n >= b:
            return f(b, floor(n / b)) + (n % b)


    for b in range(2, N):
        if f(b, N) == S:
            return b
    return -1


if __name__ == '__main__':
    res = oracle()
    print(res)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

if __name__ == '__main__':
    main()

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
for i in range(2, int(math.sqrt(n))+1):
    if f(i, n) == s:
        ans = i
        break
if ans == -1:
    for i in range(int(math.sqrt(n)), 0, -1):
        b = (n-s) // i + 1
        if f(b,n) == s:
            ans = b
            break

print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
s=int(input())
a="-1"
def f(b,n):
    if n<b:
        return n
    else:
        return f(b,n//b)+n%b
if n==s:
    a=n+1
i=2
while 0<=i<=n**(1/2):
    if f(i,n)==s:
        a=i
        break
    i+=1
if a=="-1":
    for p in range(1,int(n**(1/2))):
        b=(n-s)/p+1
        if f(b,n)==s:
            a=b
            break
print(int(a))

Submission status: Runtime Error

Solution code:
import math
#平方オーダーなら収まるので平方根とって方針を分ける
n = int(input())
s = int(input())
if n == s:
  print(n + 1)
  exit(0)
def sqrt(k):
  return int(math.sqrt(k))
def digitsum(b, m):
  if m < b:
    return m
  return digitsum(b, m // b) + m % b
#√nより小さいなら
#全探索余裕 桁は多くて40程度なので
for b in range(2, sqrt(n) + 1):
  if digitsum(b, n) == s:
    print(b)
    exit(0)
#√nより大きいなら
#b^2 > n である。２桁ということ
#2桁目がpなら、1桁目はs-pである
#pb + s - p = n
#b = (n - s) // p + 1
for p in range(1, sqrt(n)):
  b = (n - s) // p + 1
  if b == 1: continue
  if digitsum(b, n) == s:
    print((n - s) // p + 1)
    exit(0)
print(-1)

Submission status: Runtime Error

Solution code:
import math
#平方オーダーなら収まるので平方根とって方針を分ける
n = int(input())
s = int(input())
if s == 1:
  print(n)
  exit(0)
if n == s:
  print(n + 1)
  exit(0)
def sqrt(k):
  return int(math.sqrt(k))
def digitsum(b, m):
  if m < b:
    return m
  return digitsum(b, m // b) + m % b
#√nより小さいなら
#全探索余裕 桁は多くて40程度なので
for b in range(2, sqrt(n) + 1):
  if digitsum(b, n) == s:
    print(b)
    exit(0)
#√nより大きいなら
#b^2 > n である。２桁ということ
#2桁目がpなら、1桁目はs-pである
#pb + s - p = n
#b = (n - s) // p + 1
for p in range(2, sqrt(n)):
  if (n - s) % p == 0:
    b = (n - s) // p + 1
    if b == 1: continue
    if digitsum(b, n) == s:
      print((n - s) // p + 1)
      exit(0)
print(-1)

Submission status: Runtime Error

Solution code:
import math
#平方オーダーなら収まるので平方根とって方針を分ける
n = int(input())
s = int(input())
if s == 1:
  print(n)
  exit(0)
def sqrt(k):
  return int(math.sqrt(k))
def digitsum(b, m):
  if m < b:
    return m
  return digitsum(b, m // b) + m % b
#√nより小さいなら
#全探索余裕 桁は多くて40程度なので
for b in range(2, sqrt(n) + 1):
  if digitsum(b, n) == s:
    print(b)
    exit(0)
#√nより大きいなら
#b^2 > n である。２桁ということ
#2桁目がpなら、1桁目はs-pである
#pb + s - p = n
#b = (n - s) // p + 1
for p in range(2, sqrt(n)):
  if (n - s) % p == 0:
    b = (n - s) // p + 1
    if digitsum(b, n) == s:
      print((n - s) // p + 1)
      exit(0)
print(-1)

Submission status: Runtime Error

Solution code:
import sys, 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 s == n:
    print(n + 1)
    sys.exit()
elif s > n:
    print('-1')
    sys.exit()

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

for b in range(2, sqrt_n + 1):
    if f(b, n) == s:
        print(b)
        sys.exit()

for p in range(1, sqrt_n + 1):
    P = sqrt_n + 1 - p
    b = int( (n -s)/P ) + 1
    if f(b, n) == s and b >= 2:
        print(b)
        sys.exit()

print('-1')

Submission status: Runtime Error

Solution code:
import sys, math

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

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

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

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

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

print('-1')

Submission status: Runtime Error

Solution code:
n = int(input())
s = int(input())
def sub(n, b):
  r = 0
  while n > 0:
    r += n%b
    n = n//b
  return r
if s == n:
  b = n+1
  print(b)
  exit()
for b in range(2, n+1):
  if b*b > n:
    break
  s2 = sub(n, b)
  if s2 == s:
    print(b)
    exit()
bs = []
for p in range(1, n+1):
  if p*p > n:
    break
  if (n-s)%p == 0:
    b = (n-s)//p+1
    bs.append(b)
bs.sort()
for b in bs:
  s2 = sub(n, b)
  if s2 == s:
    print(b)
    exit()
print(-1)

Submission status: Runtime Error

Solution code:
n = int(input())
s = int(input())
def sub(n, b):
  r = 0
  while n > 0:
    r += n%b
    n = n//b
  return r
if s == n:
  b = n+1
  print(b)
  exit()
for b in range(2, n+1):
  if b*b > n:
    break
  s2 = sub(n, b)
  if s2 == s:
    print(b)
    exit()
bs = []
for p in range(1, n+1):
  if p*p > n:
    break
  b = (n-s)//p+1
  bs.append(b)
bs.sort()
for b in bs:
  s2 = sub(n, b)
  if s2 == s:
    print(b)
    exit()
print(-1)

Submission status: Runtime Error

Solution code:
n=int(input())
s=int(input())
if n==s:
  print(n+1)
  exit()
for b in range(2,int(n**(1/2)+1)):
  m=n
  wa=0
  while m>0:
    wa+=m%b
    m=m//b
  if wa==s:
    print(b)
    exit()

for p in range(int(n**(1/2)),0,-1):
  if (n-s)%p==0:
    b=(n-s)//p+1
    if p+n%b==s:
      print(b)
      exit()
print('-1')

Submission status: Runtime Error

Solution code:
n=int(input())
s=int(input())
if n==s:
  print(n+1)
  exit()
for b in range(2,int(n**(1/2))+1):
  m=n
  wa=0
  while m>0:
    wa+=m%b
    m=m//b
  if wa==s:
    print(b)
    exit()

for p in range(int(n**(1/2)),0,-1):
  if (n-s)%p==0:
    b=(n-s)//p+1
    if p+n%b==s:
      print(b)
      exit()
print(-1)

Submission status: Runtime Error

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

b_ans=1
for b in range(2,int(n**0.5)+1):
  nn=n
  st=[]
  while(nn>0):
    st.append(nn%b)
    nn=(nn-st[-1])/b
  
  if sum(st)==s:
    b_ans=b
    break


if b_ans==1:
  for p in range(int(n**0.5)):
    b=int(n/p)
    q=n-p*b
    if s==p+q:
      b_ans=b
      break

if b_ans!=1:
  print(b_ans)
else:
  print(-1)

Submission status: Runtime Error

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

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

    def digitSum(n, b):
        if b < 0:
            return -1
        if n < b:
            return n
        return digitSum(n // b, b) + n % b

    for b in range(2, int(N**0.5 + 10)):
        if digitSum(N, b) == S:
            print(b)
            return

    for p in range(1, int(N**0.5 + 10)):
        b = (N - S) // p + 1
        if digitSum(N, int(b)) == S:
            print(int(b))
            return
    print('-1')
sol()

Submission status: Runtime Error

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

#A
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

#B
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

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

# D
# 解説AC
# 2 <= b <= √n
# までに関しては全探索すればよくて
# ここで解がない場合はそれ以上を見る 
# √n < b <= n
# に関してはb進数表記で2桁になることが確定してて
# n = p*b+qとするなら p + q = s で(1 <= p < b, 0 <= q < b)
# n = p*b+q >= p*b > p**2 → √n > p がわかるからpを全探索
# b = (n-s)/p + 1なのでpを決めればbが決まってあとは調べればいい
# 数学じゃんこれ！ 
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 s == f(b, n):
            print(b)
            return
    print(-1)
    return


#Solve
if __name__ == '__main__':
    D()

Submission status: Runtime Error

Solution code:

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(num + 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):
        b = (num - s) // p + 1
        if check(num, s, b):
            print(b)
            sys.exit()

    print(-1)






if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
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 f(b, n) == s:
        print (b)
        exit()
print (-1)

# for i in range(2, 100):
#     print (i, f(i,100))

Submission status: Runtime Error

Solution code:
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(1, int(math.sqrt(n))+2):
    b = (n-s)//p + 1
    if f(b, n) == s:
        print (b)
        exit()
print (-1)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
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=0
  for i in range(2,int(n**0.5)+1):
    if f(i,n)==s:
      ans=i
      break
  if ans!=0:
    print(ans)
  else:
    for i in range(1,int(n**0.5)+1):
      tb=(n-s)//i+1
      if f(tb,n)==s:
        ans=tb
        break
    if ans!=0:
      print(ans)
    else:
      print(-1)

Submission status: Runtime Error

Solution code:
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(n+1)
else:
  ans=0
  for i in range(2,int(n**0.5)+1):
    if f(i,n)==s:
      ans=i
      break
  if ans!=0:
    print(ans)
  else:
    for i in range(1,int(n**0.5)+1):
      tb=(n-s)//i+1
      if f(tb,n)==s:
        ans=tb
        break
    if ans!=0:
      print(ans)
    else:
      print(-1)

Submission status: Runtime Error

Solution code:
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 == 1:
        print(n)
        return
    elif s == n:
        print(n+1)
        return
    elif s > n:
        print(-1)
        return
    sqrt = int(math.sqrt(n))
    for b in range(2, sqrt+1):
        if f(b, n) == s:
            print(b)
            return
    for x in range(sqrt, 0, -1):
        if s < x:
            continue
        y = s - x
        b = (n-y) // x
        if f(b, n) == s:
            print(b)
            return
    print(-1)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
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 == 1:
        print(n)
        return
    elif s == n:
        print(n+1)
        return
    elif s > n:
        print(-1)
        return
    sqrt = -int(-math.sqrt(n))
    b = 2
    for b in range(2, sqrt+1):
        if f(b, n) == s:
            print(b)
            return
    for x in range(sqrt, s, -1):
        y = s - x
        z = n - x
        b = z // y
        if z % y == 0 and f(b, n) == s:
            print(b)
            return
    print(-1)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
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 == 1:
        print(n)
        return
    elif s == n:
        print(n+1)
        return
    elif s > n:
        print(-1)
        return
    sqrt = -int(-math.sqrt(n))
    b = 2
    for b in range(2, sqrt+1):
        if f(b, n) == s:
            print(b)
            return
    for x in range(sqrt, 0, -1):
        y = s - x
        z = n - x
        b = z // y
        if z % y == 0 and f(b, n) == s:
            print(b)
            return
    print(-1)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys

def f(b, n):
    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 n+1

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


    for p in range(1, int(n**0.5)):
        b = (n - s) // p + 1
        if f(b, n) == s:
            return b

    return -1


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

Submission status: Runtime Error

Solution code:
import sys

def f(b, n):
    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 n+1

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

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


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

Submission status: Runtime Error

Solution code:
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 == 1:
        print(n)
        return
    elif s > n:
        print(-1)
        return
    b = 2
    while b * b <= n:
        if f(b, n) == s:
            print(b)
            return
        b += 1
    p = 1
    while p * p <= n:
        q = s - p
        b = (n - q) // p
        if f(b, n) == s:
            print(b)
            return
        p += 1
    print(-1)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

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

ans=-1
if s>n:
  pass
elif 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(1,int(n**0.5)+1):
			_b = (n-s)//_p+1
			if f(_b,n)==s:
				ans=_b
				break
print(ans)

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):
    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 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):
    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()
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 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):
    k = b
    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()
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 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
sys.setrecursionlimit(100000000)
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)[::-1]:
    if (n-s)%p == 0:
        b = (n-s)//p+1
        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