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:
from math import floor,ceil
def f(b,n):
    if n < b:
        return n
    else:
        return f(b,floor(n/b))+n%b
n = int(input())
s = int(input())

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

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

Solution code:
n = int(input())
s = int(input())
rtn = -1* int( -1 * (n**0.5))

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

if n < s or (n // 2)+1 < s < n :
    print("-1")
elif s == n:
    print(n+1)
elif s == n//2 +1:
    if n % 2 == 1:
        print(n//2 + 1)
    else:
        print("-1")
elif (n//3) + 2 < s <= n//2:
    print(n-s+1)
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+1):
        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,rtn+2):
            if f(b,n) == s:
                print(b)
                exit()
        for p in (rtn,1,-1):
            if (n-s) % p == 0:
                b = (n-s)//p + 1
                if f(b,n) == s:
                    print(b)
                    exit()
    print(n-s+1)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = int(input())
rtn = int(n**0.5)+1

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,rtn):
            if f(b,n) == s:
                print(b)
                exit()
        for p in (rtn-1,1,-1):
            if (n-s) % p == 0:
                b = (n-s)//p + 1
                if f(b,n) == s:
                    print(b)
                    exit()
    print(n-s+1)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = int(input())
rtn = int(n**0.5)+1

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,rtn):
            if f(b,n) == s:
                print(b)
                exit()
        for p in (rtn-1,1,-1):
            if (n-s) % p == 0:
                b = (n-s)//p + 1
                print(b,n,f(b,n),s)
                if f(b,n) == s:
                    print(b)
                    exit()
    print(n-s+1)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = int(input())
rtn = int(n**0.5)+1

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, 2*n//x - 2*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: Wrong Answer

Solution code:

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

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,int(n**0.5)+2):
        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: Wrong Answer

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

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//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 == 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
    if s - (n //(x+1))  <= x:
        x = x + 1
    if 3 < n/(x -1) - n/x :
        for b in range(n//x, 2*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//2)+2):
            if f(b,n) == s:
                print(b)
                exit()

    print(n-s+1)

Submission status: Wrong Answer

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 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 == 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
    if s - (n //(x+1))  <= x:
        x = x + 1
    if 3 < n/(x -1) - n/x :
        for b in range(n//x, 2*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//2)+2):
            if f(b,n) == s:
                print(b)
                exit()

    print(n-s+1)

Submission status: Wrong Answer

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
    if s - (n //(x+1))  <= x:
        x = x + 1

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

    print(n-s+1)

Submission status: Wrong Answer

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
    if (n //(x+1)) - s < x:
        x = x + 1
    if 3 < n/(x -1) - n/x :
        for b in range( n//x,n//(x-1)+1):
            if f(b,n) == s:
                print(b)
                exit()
    else:
        for b in range(2,(n//2)+2):
            if f(b,n) == s:
                print(b)
                exit()

    print(n-s+1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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)+2 < s < n:
    print("-1")
elif s == n:
    print(n+1)
elif s == 1:
    print(n)
else:
    for b in range(2,(n//2)+2):
        if f(b,n) == s:
            print(b)
            exit()
    print(n-s+1)

Submission status: Wrong Answer

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)+2 < s < n:
    print("-1")
elif s == n:
    print(n+1)
elif s == 1:
    print(n)
else:
    for b in range(2,(n//2)+2):
        if f(b,n) == s:
            print(b)
            exit()
    print("-1")

Submission status: Wrong Answer

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 :
    print("-1")
    exit()

for b in range(2,n+1):
    if s <= b:
        break
    elif f(b,n) == s:
        print(b)
        exit()
if f(n,n) == s:
    print(n)
    exit()
print("-1")

Submission status: Wrong Answer

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(N + 1)
        return
    if N < S:
        print(-1)
        return

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

    bs = set()
    t = N - S
    for i in range(1, int(sqrt(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: Wrong Answer

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
  b = (n-q) % i
  if b ==0:
    if int((n-q)/i) >= ru:
      print(int((n-q)/i))
      exit()
print(-1)

Submission status: Wrong Answer

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
  b = (n-q) % i
  if b ==0:
    print(int((n-q)/i))
    exit()
print(-1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n = int(input())
s = int(input())
if s <= (n+1)//2:
  print(n-s+1)
else:
  print(-1)

Submission status: Wrong Answer

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

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

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

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

ans = INF = float('inf')

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

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

Submission status: Wrong Answer

Solution code:
from math import sqrt

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


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

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

Submission status: Wrong Answer

Solution code:
from math import sqrt

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


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

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

Submission status: Wrong Answer

Solution code:
from math import sqrt

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


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

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

Submission status: Wrong Answer

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

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

if S == 1:
    ans = N
else:
    ans = -1

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

Submission status: Wrong Answer

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


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

exist = False
for i in range(2,n):
    if n_based(n,i) == s:
        print(i)
        exist = True
        break
    
if not exist:
    print(-1)

Submission status: Wrong Answer

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

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

    if cnd:
        return min(cnd)

    return -1


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

    print(slv(N, S))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def c(b):
    cur = n
    acc = 0
    while cur != 0:
        div, mod = divmod(cur, b)
        acc += mod
        cur = div
    return acc

def g(b):
    if b > n: return n
    return sum(divmod(n,b))

def f():
    if n == s:
        return (n + 1)
    if n < s:
        return -1
    rt = math.ceil(math.sqrt(n))
    for b in range(2, rt + 1):
        if c(b) == s: return b
    for p in range(rt, 0, -1):
        q = s - p
        x = n - q
        b = x // p
        if g(b) == s:
            return b
    return -1
    
print(f())

Submission status: Wrong Answer

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

def c(b):
    cur = n
    acc = 0
    while cur != 0:
        div, mod = divmod(cur, b)
        acc += mod
        cur = div
    return acc

def f():
    if n == s:
        return (n + 1)
    if n < s:
        return -1
    rt = math.ceil(math.sqrt(n))
    for b in range(2, rt + 1):
        if c(b) == s: return b
    for p in range(rt, 0, -1):
        q = s - p
        x = n - q
        b = x // p
        if x % p == 0 and b > q and b > p: return b
    return -1
    
print(f())

Submission status: Wrong Answer

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

def c(b):
    cur = n
    acc = 0
    while cur != 0:
        div, mod = divmod(cur, b)
        acc += mod
        cur = div
    return acc

def f():
    if n == s:
        return (n + 1)
    if n < s:
        return -1
    rt = math.ceil(math.sqrt(n))
    for b in range(2, rt + 1):
        if c(b) == s: return b
    for p in range(1, rt):
        q = s - p
        x = n - q
        b = x // p
        if x % p == 0 and b > q and b > p: return b
    return -1
    
print(f())

Submission status: Wrong Answer

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

def c(b):
    cur = n
    acc = 0
    while cur != 0:
        div, mod = divmod(cur, b)
        acc += mod
        cur = div
    return acc

def f():
    if n == s:
        return (n + 1)
    if n < s:
        return -1
    rt = math.ceil(math.sqrt(n))
    for b in range(2, rt + 1):
        if c(b) == s: return b
    for p in range(1, rt):
        q = s - p
        x = n - q
        b = x // p
        if x % p == 0 and b > q: return b
    return -1
    
print(f())

Submission status: Wrong Answer

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

def c(b):
    cur = n
    acc = 0
    while cur != 0:
        div, mod = divmod(cur, b)
        acc += mod
        cur = div
    return acc

def f():
    if n == s:
        return (n + 1)
    rt = math.sqrt(n)
    for i in range(2, math.ceil(rt + 1)):
        if c(i) == s: return i
    for p in range(1, math.ceil(rt)):
        q = s - p
        x = n - q
        b = x // p
        if x % p == 0 and b > q: return b
    return -1
    
print(f())

Submission status: Wrong Answer

Solution code:
from math import sqrt

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

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

def solve(n, s):
    if s == n:
        print(n+1)
        return
    elif n < s:
        ans = -1
    else:
        for i in range(2, int(sqrt(n))+1):
            if f(i, n) == s:
                print(i)
                return
            
        for i in range(int(sqrt(n)), 0, -1):
            b = (n-s)/i+1
            if b == int(b) and f(int(b), n) == s:
                print(int(b))
                return

        print(-1)
        return

solve(n, s)

Submission status: Wrong Answer

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
if n == s:
    print(n+1)
    exit()
if (n+1)//2 < s:
    print(-1)
    exit()

ans = float("inf")
i = 1
q = 0
while s >= i:
    q, m = divmod(n-(s-i), i)
    if i > q:
        break
    if m == 0:
        ans = q
    i += 1
i = 2
while i*i <= n:
    if f(i, n) == s:
        ans = i
        break
    i += 1
print(ans)

Submission status: Wrong Answer

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
if n == s:
    print(n+1)
    exit()
if (n+1)//2 < s:
    print(-1)
    exit()

ans = float("inf")
for i in range(1, -int(-n**0.5)):
    if s < i:
        break
    q, m = divmod(n-(s-i), i)
    if m == 0:
        ans = q
for i in range(2, int(n**0.5)+1):
    if f(i, n) == s:
        ans = i
        break

print(ans)

Submission status: Wrong Answer

Solution code:
from math import sqrt
n = int(input())
s = int(input())
def f(x,y):
	if x<=y: 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: Wrong Answer

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

for i in range(2, int((n+1)**.5)):
    c = 0
    m = n
    while m > 0:
        c += m%i
        m //= i
        if c > s:
            break
    if c == s:
        print(i)
        exit()
    else:
        pass
for i in range(int(n**.5), 1, -1):
    b = n//i
    m = n
    c = 0
    while m > 0:
        c += m%b
        m //= b
        if c > s:
            break
    if s >= c:
        if (s-c)%i == 0 and b-(s-c)//i > n//(i+1):
            print(b-(s-c)//i)
            exit()
if n == s:
    print(n+1)
elif n <= (n+1)//2:
    print(n-s+1)
elif s == 1:
    print(n)
else:
    print(-1)

Submission status: Wrong Answer

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

for i in range(2, int((n+1)**.5)):
    c = 0
    m = n
    while m > 0:
        c += m%i
        m //= i
        if c > s:
            break
    if c == s:
        print(i)
        exit()
    else:
        pass

if n == s:
    print(n+1)
elif n <= (n+1)//2:
    print(n-s+1)
elif s == 1:
    print(n)
else:
    print(-1)

Submission status: Wrong Answer

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 n < s:
  ans.append(-1)
  
else:
  rootn = int(math.sqrt(n))
  for b in range(2, rootn+1):
    if s == f(b, n):
      ans.append(b)
      break
      
  for p in range(1, rootn):
    b = (n-s)//p + 1
    if s == p + n%b:
      ans.append(b)
      
if not ans:
  ans.append(-1)

print(min(ans))

Submission status: Wrong Answer

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 n < s:
  ans.append(-1)
  
else:
  rootn = int(math.sqrt(n)) + 1
  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 + n%b:
      ans.append(b)
      
if not ans:
  ans.append(-1)

print(min(ans))