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: Wrong Answer

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 = -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
            value = digit_sum(n, start)
            key.append((start, value, end+1, i, first))
            judge = start
            start = next_start
            if start == 1:
                break

        for i in range(2, judge + 1):
            sub = digit_sum(n, i)
            if sub == s:
                ans = i
                break
        else:
            for index, start, end, i, first in reversed(key):
                if end < s or s < start:
                    continue
                if (s - first) % i:
                    continue
                ans = index - (s - first) // i
                break

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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 = -1

    elif n == s:
        ans = n + 1

    else:
        key = []
        start = n

        for i in range(1, n):
            end = start - n // i // (i + 1)
            if start == end+1:
                judge = start
                break

            while end > 1:
                if digit_sum(n, end) == i * (start - end) + start:
                    end -= 1
                    continue
                break

            next_start = end
            value = digit_sum(n, start)
            key.append((start, value, end+1, i))
            judge = start
            start = next_start
            if start == 1:
                break

        for i in range(2, judge + 1):
            sub = digit_sum(n, i)
            if sub == s:
                ans = i
                break
        else:
            for index, start, end, i in reversed(key):
                if end < s or s < start:
                    continue
                if (s - start) % i:
                    continue
                ans = index - (s - start) // i
                break

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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 = -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
            value = digit_sum(n, start)
            key.append((start, value, end, i, first))
            judge = start
            start = next_start
            if start == 1:
                break

        for i in range(2, judge + 1):
            sub = digit_sum(n, i)
            if sub == s:
                ans = i
                break
        else:
            for index, start, end, i, first in reversed(key):
                if end < s or s < start:
                    continue
                if (s - first) % i:
                    continue
                ans = index - (s - first) // i
                break

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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 = -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)
            value = digit_sum(n, start)
            key.append((start, value, end, i, first))
            judge = start
            start = next_start
            if start == 1:
                break

        for i in range(2, judge + 1):
            sub = digit_sum(n, i)
            if sub == s:
                ans = i
                break
        else:
            for index, start, end, i, first in reversed(key):
                if end < s or s < start:
                    continue
                if (s - first) % i:
                    continue
                ans = index - (s - first) // i
                break
    print(ans)
    """
    for i in range(2, ans):
        if digit_sum(n, i) == s:
            print("WA")
            print(i)
            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: Wrong Answer

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 = -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))
            judge = start
            start = next_start
            if start == 1:
                break
        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: Wrong Answer

Solution code:
def F(n, b):
    res = 0
    while n:
        n, m = divmod(n, b)
        res += m
    return res


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


inf = 10**18
ans = inf
d = 0
while True:
    d += 1
    lower = N // d
    upper = N // (d + 1) + 1
    if lower == upper:
        break
    FL = F(N, lower)
    FU = F(N, upper)
    if FL <= S <= FU:
        if (FU - S) % d == 0:
            pos = (FU - S)//d
            ans = min(ans, upper + pos)

for b in range(2, upper):
    if F(N, b) == S:
        ans = min(ans, b)

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

Submission status: Wrong Answer

Solution code:
def F(n, b):
    res = 0
    while n:
        n, m = divmod(n, b)
        res += m
    return res


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


inf = 10**18
ans = inf
d = 0
while True:
    d += 1
    lower = N // d
    upper = N // (d + 1) + 1
    if lower == upper:
        break
    FL = F(N, lower)
    FU = F(N, upper)
    if FL <= S <= FU:
        if (FU - S) % d == 0:
            pos = (FU - S)//d
            ans = min(ans, upper + pos)

for b in range(2, upper):
    if F(N, b) == S:
        ans = min(ans, b)

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

Submission status: Wrong Answer

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)
    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)&(0<=y<b):
            ans = min(ans,b)

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

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
s = int(input())
def sub(n, b):
    """nのb進数表記したときの各桁
    n = sum(pow(b,i) * ans[i])
    """
    ans = []
    while n>0:
        n,v = divmod(n, b)
        ans.append(v)
    return ans
ans = None
for b in range(2,n+1):
    if b**2>n:
        break
    if sum(sub(n, b))==s:
        ans = b
        break
if ans is None:
    ans = float("inf")
    if n==s:
        ans = s
    for p in range(1,n+1):
        if p**2>n:
            break
        if (n+p-s)%p==0:
            b = (n+p-s)//p
            q = s - p
            if b**2>n and 0<=q<b and p<b:
                ans = min(ans, b)
            else:
                continue
if ans is None or ans==float("inf"):
    ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
s = int(input())
def sub(n, b):
    """nのb進数表記したときの各桁
    n = sum(pow(b,i) * ans[i])
    """
    ans = []
    while n>0:
        n,v = divmod(n, b)
        ans.append(v)
    return ans
ans = None
for b in range(2,n+1):
    if b**2>n:
        break
    if sum(sub(n, b))==s:
        ans = b
        break
if ans is None:
    ans = float("inf")
    for p in range(1,n+1):
        if p**2>n:
            break
        if (n+p-s)%p==0:
            b = (n+p-s)//p
            q = s - p
            if b**2>n and 0<=q<b and p<b:
                ans = min(ans, b)
            else:
                continue
if ans is None or ans==float("inf"):
    ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
s = int(input())
def sub(n, b):
    """nのb進数表記したときの各桁
    n = sum(pow(b,i) * ans[i])
    """
    ans = []
    while n>0:
        n,v = divmod(n, b)
        ans.append(v)
    return ans
ans = None
for b in range(2,n+1):
    if b**2>n:
        break
    if sum(sub(n, b))==s:
        ans = b
        break
if ans is None:
    for p in range(1,n+1):
        if p**2>n:
            ans = -1
            break
        if (n+p-s)%p==0:
            b = (n+p-s)//p
            q = s - p
            if b**2>n and 0<=q<b and p<b:
                ans = b
                break
            else:
                continue
if ans is None:
    ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
def f(b, n):
  if(n< b):
    return n
  else:
    return f(b, int(n/ b))+ n% b
  
n = int(input())
s = int(input())
flag = 0

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

Submission status: Wrong Answer

Solution code:
from math import sqrt

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

def divisors(M):#Mの約数列 O(n^(0.5+e))
    import math
    d=[]
    i=1
    while math.sqrt(M)>=i:
        if M%i==0:
            d.append(i)
            if i**2!=M:
                d.append(M//i)
        i=i+1
    d.sort()
    return d

n=int(input());s=int(input())
if 0>n-s:
    print(-1)
else:
    m=int(sqrt(n))
    for b in range(2,m+1):
        if digitsum(b,n)==s:
            print(b)
            break
    else:
        d=divisors(n-s)
        for i in d:
            if i>=m+1 and s>=(n-s)//i and i+1>(s-(n-s)//i):
                print(i+1)
                break
        else:
            if n==s:
                print(n+1)
            else:
                print(-1)

Submission status: Wrong Answer

Solution code:
from math import sqrt

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

def divisors(M):#Mの約数列 O(n^(0.5+e))
    import math
    d=[]
    i=1
    while math.sqrt(M)>=i:
        if M%i==0:
            d.append(i)
            if i**2!=M:
                d.append(M//i)
        i=i+1
    d.sort()
    return d

n=int(input());s=int(input())
if 0>n-s:
    print(-1)
else:
    m=int(sqrt(n))
    for b in range(2,m+1):
        if digitsum(b,n)==s:
            print(b)
            break
    else:
        d=divisors(n-s)
        for i in d:
            if i>=m+1 and s>=(n-s)//i and i+1>(s-(n-s)//i):
                print(i+1)
                break
        else:
            print(-1)

Submission status: Wrong Answer

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

m = abs(n-s)

a = set()
i = 1
while i * i <= m:
    if m % i == 0:
        a.add(i)
        a.add(m // i)
    i += 1

for i in sorted(list(a)):
    i += 1
    su = 0
    nn = n
    while nn:
        su += nn % i
        nn //= i
    if su == s:
        print(i)
        break
else:
    print(-1)

Submission status: Wrong Answer

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
nn=n-s
if nn==0:
    print(n+1)
    exit()
ans=float('inf')
b=2
while b*b<=nn and nn>0:
    if nn%b==0:
        num=n
        su=0
        bb=nn//b
        while num>=bb:
            su+=num%bb
            num//=bb
        su+=num
        if su==s:
            ans=min(ans,bb)
        '''
        if b!=nn//b:
            bb=nn//b
            num=n
            su=0
            while num>=bb:
                su+=num%bb
                num//=b
            su+=num
            if su==s:
                ans=min(ans,bb)
        '''
    b+=1
b=nn
num=n
su=0
while num>=b and nn>0:
    su+=num%b
    num//=b
su+=num
if su==s:
    ans=min(ans,b)
b=n
num=n
su=0
while num>=b and b>1:
    su+=num%b
    num//=b
su+=num
if su==s:
    ans=min(ans,b)

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

Submission status: Wrong Answer

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(b)
    exit()
while b*b<=nn:
    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: Wrong Answer

Solution code:
n = int(input())
s = int(input())
if s == 1:
    print(n)
    exit()
b = 2
while b <= n**0.5+1:
    n1,li = n,[]
    while n1 > 0:
        li.append(n1%b)
        n1 = (n1-(n1%b))//b
    if sum(li) == s:
        print(b)
        exit()
    b +=1
print(-1)

Submission status: Wrong Answer

Solution code:
import math
import sys
N = int(input())
S = int(input())

def tt(k, N):
    r = 0
    while N:
        N, m = divmod(N, k)
        r += m
#    print(k, r)
    return r

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

for i in range(2, math.floor(N**0.5) + 2):
    if tt(i, N) == S:
        print(i)
        sys.exit()

for k in range(math.floor(N**0.5), 0, -1):
    s = N//k
    f = N//(k+1) + 1
    si = k + N%k
    fi = si + (s-f)*k
    if N//(s**2) > 0:
        continue
#    print("aaa", k, si, fi, s, f)
    if si <= S <= fi and ((S-si) % k == 0):
#        print("bb", f+(S-si)%k)
        print(f+(S-si)%k)
        sys.exit()
#    for i in range(f, s+1):
#        tt(i, N)
#        if ( i == f or i == s ) and S == tt(i, N):
#            print(i)
#            sys.exit()

print(-1)

Submission status: Wrong Answer

Solution code:
import math
import sys
N = int(input())
S = int(input())

def tt(k, N):
    r = 0
    while N:
        N, m = divmod(N, k)
        r += m
#    print(k, r)
    return r

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

for i in range(2, math.floor(N**0.5) + 2):
    if tt(i, N) == S:
        print(i)
        sys.exit()

for k in range(math.floor(N**0.5), 0, -1):
    s = N//k
    f = N//(k+1) + 1
    si = k + N%k
    fi = si + (s-f)*k
    if N//(s**2) > 0:
        continue
#    print("aaa", k, si, fi, s, f)
    if si <= S <= fi and ((S-si) % k == 0):
#        print("bb", f+(S-si)%k)
        print(f+(S-si)%k)
        sys.exit()
#    for i in range(f, s+1):
#        tt(i, N)
#        if ( i == f or i == s ) and S == tt(i, N):
#            print(i)
#            sys.exit()

print(-1)

Submission status: Wrong Answer

Solution code:
import math
import sys
N = int(input())
S = int(input())

def tt(k, N):
    r = 0
    while N:
        N, m = divmod(N, k)
        r += m
#    print(k, r)
    return r

for i in range(2, math.floor(N**0.5) + 2):
    if tt(i, N) == S:
        print(i)
        sys.exit()

for k in range(math.floor(N**0.5), 0, -1):
    s = N//k
    f = N//(k+1) + 1
    si = k + N%k
    fi = si + (s-f)*k
    if N//(s**2) > 0:
        continue
#    print("aaa", k, si, fi, s, f)
    if si <= S <= fi and ((S-si) % k == 0):
#        print("bb", f+(S-si)%k)
        print(f+(S-si)%k)
        sys.exit()
#    for i in range(f, s+1):
#        tt(i, N)
#        if ( i == f or i == s ) and S == tt(i, N):
#            print(i)
#            sys.exit()

print(-1)

Submission status: Wrong Answer

Solution code:
import math
import sys
N = int(input())
S = int(input())

def tt(k, N):
    r = 0
    while N:
        N, m = divmod(N, k)
        r += m
#    print(k, r)
    return r

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

for i in range(2, math.floor(N**0.5) + 2):
    if tt(i, N) == S:
        print(i)
        sys.exit()

for k in range(math.floor(N**0.5), 0, -1):
    s = N//k
    f = N//(k+1) + 1
    si = k + N%k
    fi = si + (s-f)*k
    if N//(s**2) > 0:
        continue
#    print("aaa", k, si, fi, s, f)
    if si <= S <= fi and ((S-si) % k == 0):
#        print("bb", f+(S-si)%k)
        print(f+(S-si)%k)
        sys.exit()
#    for i in range(f, s+1):
#        tt(i, N)
#        if ( i == f or i == s ) and S == tt(i, N):
#            print(i)
#            sys.exit()
print(-1)

Submission status: Wrong Answer

Solution code:
import math
import sys
N = int(input())
S = int(input())

def tt(k, N):
    r = 0
    while N:
        N, m = divmod(N, k)
        r += m
#    print(k, r)
    return r

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

for i in range(2, math.floor(N**0.5) + 2):
    if tt(i, N) == S:
        print(i)
#        sys.exit()

for k in range(math.floor(N**0.5), 0, -1):
    s = N//k
    f = N//(k+1) + 1
    si = k + N%k
    fi = si + (s-f)*k
    if N//(s**2) > 0:
        continue
#    print("aaa", k, si, fi, s, f)
    if si <= S <= fi and ((S-si) % k == 0):
#        print("bb", f+(S-si)%k)
        print(f+(S-si)%k)
        sys.exit()
#    for i in range(f, s+1):
#        tt(i, N)
#        if ( i == f or i == s ) and S == tt(i, N):
#            print(i)
#            sys.exit()
print(-1)

Submission status: Wrong Answer

Solution code:
n=int(input())
s=int(input())
if s==n:
    print(1)
    exit()
    
for i in range(2,4*(10**5)):
    N=n
    S=0
    if i==2:
        for j in range(40):
            S+=N//(i**(39-j))
            N%=(i**(39-j))
        #print(i,int(S))
        if s==S:
            print(i)
            exit()
    elif i==3:
        for j in range(25):
            S+=N//(i**(39-j))
            N%=(i**(39-j))
        #print(i,int(S))
        if s==S:
            print(i)
            exit()
    else:
        for j in range(20):
            S+=N//(i**(39-j))
            N%=(i**(39-j))
        #print(i,int(S))
        if s==S:
            print(i)
            exit()
print(-1)

Submission status: Wrong Answer

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

if s==n:
    print(1)
    exit()
elif s==1:
    print(n)
for i in range(2,10**6):
    N=n
    S=0
    for j in range(40):
        S+=N//(i**(39-j))
        N%=(i**(39-j))
    #print(i,int(S))
    if s==S:
        print(i)
        exit()
print(-1)

Submission status: Wrong Answer

Solution code:
import math

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()

i = 2
while i * i <= N:
    if f(i, N) == S:
        print(i)
        exit()
    i += 1

sqrtN = math.floor(math.sqrt(N))
i = 1
while i * i < N:
    if (N - S) % i != 0:
        i += 1
        continue
    b = (N - S) // i + 1
    if sqrtN < b and f(b, N) == S:
        print(b)
        exit()
    i += 1

print(-1)

Submission status: Wrong Answer

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()

i = 2
while i * i <= N:
    if f(i, N) == S:
        print(i)
        exit()
    i += 1

i = 1
while i * i < N:
    if (N - S) % i != 0:
        i += 1
        continue
    b = (N - S) // i + 1
    if 2 <= b and f(b, N) == S:
        print(b)
        exit()
    i += 1

print(-1)

Submission status: Wrong Answer

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()

i = 2
while i * i <= N:
    if f(i, N) == S:
        print(i)
        exit()
    i += 1

i = 1
while i * i < N:
    b = (N - S) // i + 1
    if 2 <= b and f(b, N) == S:
        print(b)
        exit()
    i += 1

print(-1)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def f(n,b):
        if n < b:
            return n
        return f(n//b, b)+(n%b)
    n,s = IR(2)
    for b in range(2,10**6+2):
        if f(n,b) == s:
            print(b)
            return
    if n <= 10**6:
        print(-1)
        return
    N = 10**6+1
    for i in range(1,N)[::-1]:
        l = (n//(i+1))+1
        r = (n//i)+1
        while r-l > 1:
            m = (l+r) >> 1
            fx = f(n,m)
            if fx >= s:
                l = m
            else:
                r = m
        if f(n,l) == s:
            print(l)
            return
    print(-1)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def f(n,b):
        if n < b:
            return n
        return f(n//b, b)+(n%b)
    n,s = IR(2)
    for b in range(2,10**6+2):
        if f(n,b) == s:
            print(b)
            return
    if n < 10**6:
        print(-1)
        return
    N = 10**6+1
    for i in range(1,N)[::-1]:
        l = (n//(i+1))+1
        r = (n//i)+1
        while r-l > 1:
            m = (l+r) >> 1
            fx = f(n,m)
            if fx >= s:
                l = m
            else:
                r = m
        if f(n,l) == s:
            print(l)
            return
    print(-1)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def f(n,b):
        if n < b:
            return n
        return f(n//b, b)+(n%b)
    n,s = IR(2)
    for b in range(2,10**6+1):
        if f(n,b) == s:
            print(b)
            return
    if n < 10**6:
        print(-1)
        return
    N = 10**6+1
    for i in range(1,N)[::-1]:
        l = (n//(i+1))+1
        r = (n//i)+1
        while r-l > 1:
            m = (l+r) >> 1
            fx = f(n,m)
            if fx >= s:
                l = m
            else:
                r = m
        if f(n,l) == s:
            print(l)
            return
    print(-1)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def f(n,b):
        if n < b:
            return n
        return f(n//b, b)+(n%b)
    n,s = IR(2)
    for b in range(2,10**6+1):
        if f(n,b) == s:
            print(b)
            return
    if n < 10**6:
        print(-1)
        return
    N = math.ceil(n/10**6)+2
    for i in range(1,N)[::-1]:
        l = (n//(i+1))+1
        r = (n//i)+1
        while r-l > 1:
            m = (l+r) >> 1
            fx = f(n,m)
            if fx >= s:
                l = m
            else:
                r = m
        if f(n,l) == s:
            print(l)
            return
    print(-1)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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 b == 1:
        continue
    if f(b, n) == s:
        ans = min(b, ans)

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

Submission status: Wrong Answer

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 b == 1:
        continue
    if f(b, n) == s:
        ans = min(b, ans)

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

Submission status: Wrong Answer

Solution code:
import math
import sys
n=int(input())
s=int(input())
root=int(math.ceil(math.sqrt(n)))

buf=10**12
if s==n:
    print(n+1)
    sys.exit()
for i in range(1,root):
    res=s-i
    x=(n-res)//i
    if x*i+res==n and x>1 and x>res:
        #print(x,i,res,s,n)
        buf=min(buf,x)
#print(buf)
for i in range(2,root+1):
    count=0
    b=n
    while(b!=0):
        count+=b%i
        b=b//i
    if count==s:
        buf=i
        break
print(buf if buf!=10**12 else -1)