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 sys
input = sys.stdin.readline

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

def main():
    n = int(input())
    s = int(input())
    
    ans = -1
    if n == s:
        ans = n + 1
    else:
        for b in range(2, int(n**0.5) + 1):
            if digit_sum(n, b) == s:
                ans = b
                break
        
        else:
            for p in range(1, int(n**0.5)+1):
                b = (n - s) // p + 1
                if digit_sum(n, b) == s:
                    ans = b
                    break
    
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

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

def main():
    n = int(input())
    s = int(input())
    ans = -1
    if n < s:
        ans = -1
    elif n == s:
        ans = n + 1
    else:
        key = []
        start, first = n, 1

        for i in range(1, n):
            first = digit_sum(n, start)
            end = start - n // i // (i + 1)
            if start == end+1:
                judge = start
                break
            while end > 1:
                if digit_sum(n, end) == i * (start - end) + first:
                    end -= 1
                    continue
                break
            next_start = end - 1
            end = digit_sum(n, end)
            key.append((start, end, i, first))
            start = next_start
            judge = end
        for i in range(2, judge + 1):
            sub = digit_sum(n, i)
            if sub == s:
                ans = i
                break
        else:
            for start, end, i, first in reversed(key):
                if end < s:
                    continue
                if (s - first) % i:
                    continue
                ans = start - (s - first) // i
                break
    print(ans)
    
    for i in range(2, ans):
        if digit_sum(n, i) == s:
            print("WA")
            print(i)
            print(3/0)
            break


def judge():
    n = int(input())
    for i in range(2, min(n+5, 1000)):
        ans = digit_sum(n, i)
        print(str(i).zfill(3), ans)
    
#judge()
main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

def digit_sum(n, b):
    if n < b:
        return n
    res = n % b + digit_sum(n // b, b)
    return res

def main():
    n = int(input())
    s = int(input())
    if n < s:
        ans = -1
    elif n == s:
        ans = n + 1
    else:
        key = []
        start, first = n, 1

        for i in range(1, n):
            first = digit_sum(n, start)
            end = start - n // i // (i + 1)
            if start == end:
                judge = end
                break
            while True:
                if digit_sum(n, end) == i * (start - end) + first:
                    end -= 1
                    continue
                break
            next_start = end - 1
            end = digit_sum(n, end)
            key.append((start, end, i, first))
            start = next_start
        for i in range(2, judge + 1):
            sub = digit_sum(n, i)
            if sub == s:
                ans = i
                break
        else:
            for start, end, i, first in reversed(key):
                if end < s:
                    continue
                if (s - first) % i:
                    continue
                ans = start - (s - first) // i
                break
    try:
        print(ans)
    except:
        print(-1)


def judge():
    n = int(input())
    for i in range(2, min(n+5, 1000)):
        ans = digit_sum(n, i)
        print(str(i).zfill(3), ans)
    
#judge()
main()

Submission status: Runtime Error

Solution code:
n = int(input())
s = int(input())
if(n<s):
    print(-1)
    exit()
elif(n==s):
    print(n+1)
    exit()
elif(s==1):
    print(n+1)
    exit()

lim = 10**6
for i in range(2,lim+1):
    tmp = 0
    x = n
    while(x > 0):
        tmp += x%i
        x //= i
    if(tmp==s):
        print(i)
        exit()

#2桁
ns = n-s
inf = 10**12
ans = inf
for i in range(1,ns+1):
    if(i**2 > ns):
        break

    if(ns%i==0):
        b = ns//i + 1
        y = n-b*i
        if(i+y==s)&(y<b):
            ans = min(ans,j+1)

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

Submission status: Runtime Error

Solution code:
import sys

MAX = 1000000


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


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

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

    ans = -1

    for b in range(2, min(n + 1, MAX) + 1):
        sm = digit_sum(n, b)
        if sm == s:
            ans = b
            break

    if not ans == -1:
        print(ans)
        sys.exit()

    if n + 1 <= MAX:
        print(-1)
        sys.exit()

    for p in reversed(range(MAX)):
        if (n - s) % p != 0:
            continue
        b = (n - s) // p + 1
        sm = digit_sum(n, b)
        if sm == s:
            ans = b
            break

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys

MAX = 1000000


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


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

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

    ans = -1

    for b in range(2, min(n + 1, MAX) + 1):
        sm = digit_sum(n, b)
        if sm == s:
            ans = b
            break

    if not ans == -1:
        print(ans)
        sys.exit()

    if n + 1 <= MAX:
        print(-1)
        sys.exit()

    for p in reversed(range(MAX)):
        if (n - s) % p != 0:
            continue
        b = (n - s) / p + 1
        sm = digit_sum(n, b)
        if sm == s:
            ans = b
            break

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n=int(input())
s=int(input())
import math
#first solve assuming b<=sqrt(n)
sq=int(math.sqrt(n))
for b in range(2,sq+2):
    num=n
    su=0
    while num>=b:
        su+=num%b
        num//=b
    su+=num
    if su==s:
        print(b)
        exit()
#answer not found yet so check in the divisors of n-s
b=1 
nn=n-s
if nn==0:
    print(n+1)
    exit()
b=int(math.sqrt(nn))
b+=1
while b>1:
    if nn%b==0:
        num=n
        bb=nn/b
        su=0
        while num>=bb:
            su+=num%bb
            num//=bb
        su+=num
        if su==s:
            print(bb)
            exit()
    b-=1

print(-1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

def solve():
    N, S = map(int, open(0))

    if N == S:
        return N + 1

    sqr = int(N ** 0.5)

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

    M = N - S
    for p in reversed(range(1, sqr + 1)):
        b = M // p + 1
        if f(b, N) == S:
            return b

    return -1

print(solve())

Submission status: Runtime Error

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

def solve():
    N, S = map(int, open(0))

    if N == S:
        return N + 1

    sqr = int(N ** 0.5)

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

    M = N - S
    for p in reversed(range(1, sqr + 1)):
        b = M // p + 1
        if f(b, N) == S:
            return b

    return -1

print(solve())

Submission status: Runtime Error

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

def f(B, N):
    X, res = N, 0
    while 0 < X:
        res += X % B
        X //= B
    return res


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

for i in range(2, N):
    if N < i * i: break
    if f(i, N) == S:
        print(i)
        exit()

for i in range(1, N):
    if N < i * i: break
    b = (N - S) // i + 1
    if f(b, N) == S:
        print(b)
        exit()

print(-1)

Submission status: Runtime Error

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

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

for i in range(2, int(n**0.5) + 3):
    if f(i, n) == s:
        print(i)
        exit()

ans = 10**12
for k in range(1, int(n**0.5) + 3):
    if (n-s) % k != 0 or n-s < 0:
        continue
    b = (n-s)//k + 1
    if f(b, n) == s:
        ans = min(b, ans)

if ans != 10**12:
    print(ans)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import math

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

if n == 1:
    if s == 1:
        print(2)
    else:
        print(-1)
    exit()

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

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


def ds(N, b):
    ret = 0
    while True:
        N, mod = divmod(N, b)
        ret += mod
        if N == 0:
            return ret


for i in range(2, math.floor(n**(1/2)) + 1):
    if ds(n, i) == s:
        print(i)
        exit()

c = n // (i + 1)
for i in range(c, 0, -1):
    if (n-s) % i == 0:
        b = (n-s)//i + 1
        if i < b and 0 <= s-i < b:
            print(b)
            exit()

print(-1)

Submission status: Runtime Error

Solution code:
import math

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

if n == 1:
    if s == 1:
        print(2)
    else:
        print(-1)
    exit()

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


def ds(N, b):
    ret = 0
    while True:
        N, mod = divmod(N, b)
        ret += mod
        if N == 0:
            return ret


for i in range(2, math.floor(n**(1/2)) + 1):
    if ds(n, i) == s:
        print(i)
        exit()

c = n // (i + 1)
for i in range(c, 0, -1):
    if (n-s) % i == 0:
        b = (n-s)//i + 1
        if i < b and 0 <= s-i < b:
            print(b)
            exit()

print(-1)

Submission status: Runtime Error

Solution code:
import math

N = int(input())
S = int(input())
L = N-S

def search(b, n=N):
    ans = 0
    while n >= b:
        ans += n%b
        n //= b
    ans += n
    return ans
s
if L < 0:
    print(-1)
elif L == 0:
    print(1)
else:
    P = []
    for l in range(1, int(math.sqrt(L))+1):
        if L%l == 0:
            P.append(l+1)
            P.append(L//l+1)
    P.sort()

    ans = -1
    for p in P:
        S0 = search(p)
        if S == S0:
            ans = p
            break

    print(ans)

Submission status: Runtime Error

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

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

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

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

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

ans = float('inf')

for b in range(2, int(N**0.5) + 10):
    if f(b, N) == S:
        ans = min(ans, b)

    q = S - b
    b = (N - q) // b
    if f(b, N) == S:
        ans = min(ans, b)

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

Submission status: Runtime Error

Solution code:
from math import sqrt, factorial
from sys import setrecursionlimit
setrecursionlimit(100000)

def inpl(): return list(map(int, input().split()))
N = int(input())
S = int(input())

RN = int(sqrt(N))
RN += ((RN+1)**2 == N)

def func(b, N):
    tmp = 0
    while N:
        N, d = divmod(N, b)
        tmp += d
    return tmp

for b in range(2, RN+1):
    tmp = func(b, N)
    if tmp == S:
        print(b)
        break
else:
    for x in range(1, RN+1):
        num = N-S+x
        if num%x:
            continue
        b = num//x
        if N//b + N%b == S:
            print(b)
            break
    else:
        print(-1)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10**9)

def f(b, n):
    if n < b:
        return n
    else:
        q, r = divmod(n, b)
        return f(b, q) + r

n = int(input())
s = int(input())
if n == s:
    print(n+1)
else:
    b = 2
    while b*b <= n:
        if f(b, n) == s:
            print(b)
            break
        b += 1
    else:
        p = 1
        ans = 10**13
        while p*p <= n:
            b = (n - s) // p + 1
            if f(b, n) == s:
                ans = min(ans, b)
            p += 1
        if ans == 10**13:
            print(-1)
        else:
            print(ans)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10000)

def f(b, n):
    if n < b:
        return n
    else:
        q, r = divmod(n, b)
        return f(b, q) + r

n = int(input())
s = int(input())
if n == s:
    print(n+1)
else:
    b = 2
    while b*b <= n:
        if f(b, n) == s:
            print(b)
            break
        b += 1
    else:
        p = 1
        ans = 10**13
        while p*p <= n:
            b = (n - s) // p + 1
            if f(b, n) == s:
                ans = min(ans, b)
            p += 1
        if ans == 10**13:
            print(-1)
        else:
            print(ans)

Submission status: Runtime Error

Solution code:
def f(b, n):
    if n < b:
        return n
    else:
        q, r = divmod(n, b)
        return f(b, q) + r

n = int(input())
s = int(input())
if n == s:
    print(n+1)
else:
    b = 2
    while b*b <= n:
        if f(b, n) == s:
            print(b)
            break
        b += 1
    else:
        p = 1
        ans = 10**13
        while p*p <= n:
            b = (n - s) // p + 1
            if f(b, n) == s:
                ans = min(ans, b)
            p += 1
        if ans == 10**13:
            print(-1)
        else:
            print(ans)

Submission status: Runtime Error

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

n = int(input())
s = int(input())
l = []

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

for i in range(1,11):
    l.append(f(10**i,n))
# print(l)
lf,ri = 0,0
for i in range(9):
    if l[i] <= s < l[i+1]:
        lf = 10**(i+1)
        ri = 10**(i+2)
else:
    lf = 2
    ri = 10

# print(lf,ri)

for b in range(lf, ri+1):
    if(f(b,n)==s):
        print(b)
        break
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import numpy as np
def f(b, n):
    s = 0
    while n > 0:
        s += n % b
        n //= b
    return s

INF = int("inf")
def solve(n, s):
    if n < s:
        return -1
    if n == s:
        return n+1
    m = int(np.sqrt(n)) + 1
    for b in range(2, m+1):
        if f(b, n) == s:
            return b
    best = INF
    for p in range(1, m+1):
        q = s - p
        if (n - q) % p != 0:
            continue
        b = (n - q) // p
        if (b > 1) and (f(b, n) == s):
            best = min(best, s)
    return -1 if (best == INF) else best

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

Submission status: Runtime Error

Solution code:
import numpy as np
def f(b, n):
    if n < b:
        return n
    else:
        n2 = n // b
        if n2 == n:
            return -1
        else:
            return f(b, n2) + (n % b)

def solve(n, s):
    if s == n:
        return n + 1
    m = int(np.sqrt(n)) + 1
    for b in range(2, m):
        if f(b, n) == s:
            return b
    for p in range(1, m):
        q = s - p
        if (n - q) % p != 0:
            continue
        b = (n - q) // p
        if f(b, n) == s:
            return b
    return -1

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

Submission status: Runtime Error

Solution code:
import itertools
import math 

n,s = [int(input()) for _ in range(2)]

def n_base_sum(n,b):
    if(int(n/b)):
        return n_base_sum(int(n/b),b)+n%b
    else:
        return n%b

def search_p(n,s):
    for p in range(math.ceil(math.sqrt(n))+1,0,-1):
        b = n //p
        q = n % b
        if p+q ==s:
            return b
    return -1

ans =-1
flag = False
answers = []
if s == n:
    ans = n+1
    flag =True
    answers.append(ans)
for b in  range(2,math.ceil(math.sqrt(n))+1):
    if s== n_base_sum(n,b):
        ans = b
        flag = True
        answers.append(ans)
        break
ans = search_p(n,s)
if ans != -1:
    flag =True
    answers.append(ans)


if not flag:
    print(-1)
else:
    print(int(min(answers)))

Submission status: Runtime Error

Solution code:
import itertools
import math 

n,s = [int(input()) for _ in range(2)]

def n_base_sum(n,b):
    if(int(n/b)):
        return n_base_sum(int(n/b),b)+n%b
    else:
        return n%b

def search_p(n,s):
    for p in range(math.ceil(math.sqrt(n))+1,0,-1):
        b = (n-s)//p + 1
        q = n % b
        if p+q ==s:
            return b
    return -1

ans =-1
flag = False
answers = []
if s == n:
    ans = n+1
    flag =True
    answers.append(ans)
for b in  range(2,math.ceil(math.sqrt(n))+1):
    if s== n_base_sum(n,b):
        ans = b
        flag = True
        answers.append(ans)
        break
ans = search_p(n,s)
if ans != -1:
    flag =True
    answers.append(ans)


if not flag:
    print(-1)
else:
    print(int(min(answers)))

Submission status: Runtime Error

Solution code:
import itertools
import math 

n,s = [int(input()) for _ in range(2)]

def calc_s(b,n):
    i = 0
    s = 0
    while(1):
        s+= n %b
        n = math.floor(n/b)
        i+=1
        if n ==0:
            break
    return s

def search_p(n,s):
    for p in range(1,math.ceil(math.sqrt(n))+1):
        b = n//p
        q = n - b*p
        if p+q ==s:
            return b
    return -1

if s == n:
    ans = n+1
elif s < math.sqrt(n):
    flag = False
    for b in  range(2,math.ceil(math.sqrt(n))+1):
        if s== calc_s(b,n):
            ans = b
            flag = True
            break
    if flag == False:
        ans = search_p(n,s)
print(ans)

Submission status: Runtime Error

Solution code:
n=int(input());s=int(input())
def f(s,t):
    c=0
    while s!=0:
        c+=s%t
        s//=t
    return c
for i in range(2,int(n**0.5)+1):
    if n%(i-1)==s%(i-1):
        if f(n,i)==s:
            print(i)
            break
else:
    for i in range(int(n**0.5)+1,0,-1):
        if (n-s)%i==0:
            b=(n-s)//i+1
            if i+n%b==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(s,t):
    c=0
    while s!=0:
        c+=s%t
        s//=t
    return c
for i in range(2,int(n**0.5)+1):
    if n%(i-1)==s%(i-1):
        if f(n,i)==s:
            print(i)
            break
else:
    for i in range(int(n**0.5)+1,0,-1):
        if (n-s)%i==0:
            b=(n-s)//i+1
            if i+n%b==s:
                print(b)
                break
    else:
        print(-1)

Submission status: Runtime Error

Solution code:
n=int(input());s=int(input())
def f(s,t):
    c=0
    while s!=0:
        c+=s%t
        s//=t
    return c
for i in range(2,int(n**0.5)+1):
    if n%(i-1)==s%(i-1):
        if f(n,i)==s:
            print(i)
            break
else:
    for i in range(int(n**0.5)+1,0,-1):
        if (n-s)%i==0:
            b=(n-s)//i+1
            if i+n//b==s:
                print(b)
    else:
        print(-1)

Submission status: Runtime Error

Solution code:
#入力
def f(n, b):
    if n < b:
        return n
    else:
        return f(n//b, b) + n % b

n = int(input())
s = int(input())
ans = 0
if s == n:
    ans = n + 1
else:
    for b in range(2, int(n**(1/2)) + 2):
        if f(n, b) == s:
            ans = b
            break

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

if ans == 0:
    ans = -1

print(ans)

Submission status: Runtime Error

Solution code:
#入力
def f(n, b):
    if n < b:
        return n
    else:
        return f(n//b, b) + n % b

n = int(input())
s = int(input())
ans = 0
if s == n:
    ans = n + 1
else:
    for b in range(2, int(n**(1/2)) + 2):
        if f(n, b) == s:
            ans = b
            break
    
    if ans == 0:
        for p in range(1, int(n**(1/2)) + 2):
            if (n-s) % p == 0:
                b = (n-s)//p + 1
            
            else:
                continue
            
            if f(n,b) == s:
                ans = b
                break
if ans == 0:
    ans = -1

print(ans)

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

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

print(-1)

Submission status: Runtime Error

Solution code:
from math import sqrt
import sys
sys.setrecursionlimit(10**6)
def f(b, n):
	if n < b:
		return n
	else:
		return f(b, n // b) + n % b

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

if n < s:
	print(-1)
divs = []
for i in range(1, int(sqrt(n-s))+1):
	if (n-s)%i == 0:
		if i>2:
			divs.append(i)
		if i != (n-s)//i:
			divs.append((n-s)//i)
divs.sort()
for d in divs:
	if f(d+1, n) == s:
		print(d+1)
		break
else:
	print(-1)

Submission status: Runtime Error

Solution code:
from math import floor
from math import sqrt

def f(bb,nn):
    if(nn<bb): return nn
    else: return f(bb,floor(nn/bb))+(nn%bb)
        

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

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

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

ans=10**12
for i in range(1,int(sqrt(n))):
    tmpb=(n-s)/i+1
    if f(tmpb,n)==s: 
        tmpb=min(ans,tmpb)

if ans>=10**12:
    print(-1)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

n = int(input())
s = int(input())
flag=False
for i in range(2,int(np.sqrt(n))+1):
    score = 0
    n1=n
    while n1!=0:
        score+=(n1%i)
        n1=int(n1/i)
    if score==s:
        flag=True
        break

if flag:
    print(i)
else:
    for i in range(1,int(np.sqrt(n))+1):
        b = (n-s)/i+1
        if int(b)==b:
            b=int(b)
            score = 0
            n1=n
            while n1!=0:
                score+=(n1%b)
                n1=int(n1/b)
            if score==s:
                flag=True
                break
    if flag:
        print(b)
    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)
N=int(input())
S=int(input())
if N==S:
    print(N+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))+2):
        b=(N-S)//(p+1)
        if f(b,N)==S:
            print(b)
            exit()
    print(-1)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
s = int(input())

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

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

b = 2
while b*b<n:
    if f(b,n)==s:
        print(b)
        exit()
    b += 1

p = 1
while p*p<n:
    q = s - p
    b = (n-q)//p
    if f(b,n)==s:
        print(b)
        exit()
    p += 1
print(-1)

Submission status: Runtime Error

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

    b = 2
    while b**2 < n:
        if f(b, n) == s:
            return b

        b += 1

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

    return -1


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

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

def solve():
    n = int(input())
    s = int(input())
    result = digit_sum(n, s)
    print(result)

solve()

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import math

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

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

ans = -1
if n == s:
    ans = n + 1
else:
    for b in range(2, math.floor(n ** 0.5) + 1):
        if f(b, n) == s:
            ans = b
            break
    else:
        for p in range(1, math.ceil(n ** 0.5))[::-1]:
            b = (n - s) // p + 1
            if b != int(b):
                continue
            if f(b, n) == s:
                ans = b
                break
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

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

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

sqrt_n = int(n ** 0.5)
ans = -1
if n == s:
    ans = n + 1
else:
    for b in range(2, sqrt_n + 1):
        if f(b, n) == s:
            ans = b
            break
    else:
        for p in range(1, sqrt_n):
            if (n - s) % p != 0:
                continue
            b = (n - s) // p + 1
            if f(b, n) == s:
                ans = b
                break
print(ans)

Submission status: Runtime Error

Solution code:
import math

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

n = input()
s = input()
ans = 1e18
if n == s:
    print n+1
    sys.exit()
if n < s:
    print -1
    sys.exit()
for i in range(2,int(math.sqrt(n))+1):
    if f(i, n) == s:
        ans = min(ans, i);
for p in range(1,int(math.sqrt(n))+1):
    if (n-s)%p != 0:
        continue
    b = ((n-s)/p)+1
    if f(b, n) == s:
        ans = min(ans, b);
if ans == 1e18:
    ans = -1
print ans