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 math

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

ans = []

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

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

elif s == 1:
  ans.append(n)
  
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))

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

print(min(ans))

Submission status: Wrong Answer

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

ans = -1

if n == s:
  ans = 1
  
if n == 1:
  ans = n
  
elif s <= -(-n//2):
  ans = n-(s-1)

print(ans)

Submission status: Wrong Answer

Solution code:
import math

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

Submission status: Wrong Answer

Solution code:
import math

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

Submission status: Wrong Answer

Solution code:
import math

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

Submission status: Wrong Answer

Solution code:
import math

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000)

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

def f(c, m):
    if m < c:
        return m
    else:
        return(f(c, m // c) + m % c)
    
b = 2

while f(b, n) != s:
    if b >= n:
        print("-1")
        sys.exit()
    else:
        b += 1
        
print(b)

Submission status: Wrong Answer

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

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

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


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



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


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

print -1

Submission status: Wrong Answer

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

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

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


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



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


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

print -1

Submission status: Wrong Answer

Solution code:
import sys
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(0)
if n < s:
    print(-1)
    sys.exit(0)
     
ans = None
for i in range(2, n):
    if i * i > n:
        break
    if f(i, n) == s:
        ans = i
        break

for i in range(1, n):
    if i * i > n:
        break
    if (n - s) % i == 0:
        if ans is None:
            ans = (n - s) // i + 1
        else:
            ans = min((ans, (n - s) // i + 1))

if ans is None:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
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(0)
if n < s:
    print(-1)
    sys.exit(0)
     
ans = None
for i in range(2, n):
    if i * i > n:
        break
    if f(i, n) == s:
        ans = i
        break
for i in range(1, n):
    if i * i > n:
        break
    if (n - s) % i == 0:
        ans = (n - s) // i + 1
        break
if ans is None:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
def d_DigitSum(N, S):
    if S == N:
        # f(b,N)=Nを満たすbはN+1が最小
        return N + 1
    if S > N:
        return -1

    from math import sqrt, floor, ceil

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

    sn = ceil(sqrt(N))
    # 2<=b<=√Nまで探索
    for b in range(2, sn + 1):
        if f(b, N) == S:
            return b
    # √N<=b<=Nまで探索
    for p in range(1, sn + 1):
        if (N - S) % p == 0:
            b = (N - S) // p + 1
            if f(b, N) == S:
                return b
    return -1
N = int(input())
S = int(input())
print(d_DigitSum(N, S))

Submission status: Wrong Answer

Solution code:
import math
import sys

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

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

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

sn = math.ceil(math.sqrt(n))
for i in range(2, sn+1):
    if f(i, n) == s:
        print(i)
        sys.exit(0)

for i in range(1, sn+1):
    if (n - s) % i == 0:
        b = (n-s)//i + 1
        if b >= 2 and f(b, b * i + n%b) == s:
            print(b)
            sys.exit(0)
if s == n:
    print(n+1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import math
import sys

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

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

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

sn = math.ceil(math.sqrt(n))
for i in range(2, sn):
    if f(i, n) == s:
        print(i)
        sys.exit(0)

for i in range(1, sn):
    if (n - s) % i == 0:
        b = (n-s)//i + 1
        if b >= 2 and f(b + n%b, n) == s:
            print(b)
            sys.exit(0)
if s == n:
    print(n+1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
import math

sys.setrecursionlimit(100000000)

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

Submission status: Wrong Answer

Solution code:
import sys
import math

sys.setrecursionlimit(100000000)

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(-1)
elif s==n:
    print(s+1)
else:
    for b in range(2, 2*(math.ceil(math.sqrt(n))+1)):
        if f(b, n)==s:
            print(b)
            break
    else:
        if f(n+1-s, n)==s:
            print(n+1-s)
        else:
            print(-1)

Submission status: Wrong Answer

Solution code:
import sys
import math

sys.setrecursionlimit(100000000)

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

def run():
    n = int(raw_input())
    s = int(raw_input())
    if s == 1:
        return n
    lb, ub = 2, s
    for k in range(1000):
        b = (lb + ub) / 2
        t = f(b, n)
        if   t > s:
            ub = b
        elif t < s:
            lb = b
        else: # s == t
            return b
    return -1

print run()

Submission status: Wrong Answer

Solution code:

import math

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

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

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

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

for p in list(range(1, min(int(math.sqrt(n))+1, s+1)))[::-1]:
    q = s - p
    if (n - q) % p == 0:
        b = (n - q) // p
        print(b)
        exit()

print(-1)

Submission status: Wrong Answer

Solution code:

import math

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

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

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

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

for p in list(range(1, int(math.sqrt(n))+1))[::-1]:
    q = s - p
    if (n - q) % p == 0:
        b = (n - q) // p
        print(b)
        exit()

print(-1)

Submission status: Wrong Answer

Solution code:

import math

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

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

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

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

for p in range(1, int(math.sqrt(n))):
    q = s - p
    if (n - q) % p == 0:
        b = (n - q) // p
        if f(b, n) == s:
            print(b)
            exit()

print(-1)

Submission status: Wrong Answer

Solution code:

import math

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

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

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

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

for p in range(1, int(math.sqrt(n))):
    q = s - p
    if (n - q) % p == 0:
        b = (n - q) // p
        if f(b, n) == s:
            print(b, p, q)
            exit()

print(-1)

Submission status: Wrong Answer

Solution code:
import math, sys

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

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

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

print("-1")

Submission status: Wrong Answer

Solution code:
import math, sys

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

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

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

print("-1")

Submission status: Wrong Answer

Solution code:
import math, sys

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

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

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

print("-1")

Submission status: Wrong Answer

Solution code:
import math, sys

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

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

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

print("-1")

Submission status: Wrong Answer

Solution code:
import sys
import math


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


n = int(sys.stdin.readline())
s = int(sys.stdin.readline())
if n == s:
    print n + 1
else:
    rn = int(math.pow(n, 0.5))
    for i in xrange(2, rn):
        if s == calc(i, n):
            print i
            break
    else:
        for i in xrange(rn):
            p = rn - i
            b = (n - s) / p + 1
            if b - int(b) == 0 and b > rn:
                if calc(b, n) == s:
                    print b
                    break
        else:
            print -1

Submission status: Wrong Answer

Solution code:
import sys
import math


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


n = int(sys.stdin.readline())
s = int(sys.stdin.readline())
if n == s:
    print n+1
else:
    rn = int(math.pow(n, 0.5))
    i = 2
    while i <= rn:
        if s == calc(i, n):
            print i
            break
        i += 1
    else:
        q = s / i
        while q < rn:
            p = s % i
            b = (n - s) / p + 1
            if s == calc(b, n):
                print b
                break
            i += 1
            q = s / i
        else:
            print -1

Submission status: Wrong Answer

Solution code:
import math as ma

def func(b, n):
	if b > n:
		return n
	else:
		return func(b, ma.floor(n/b)) + n % b
		
N = int(input())
S = int(input())

flag = False

for i in range(2,ma.ceil(ma.sqrt(N))):
	if func(i, N) == S:
		print(i)
		flag = True
		break

if flag == False:
	for j in range(1, ma.ceil(ma.sqrt(N))):
		b = (N-S)/j + 1
		if func(b,N) == S:
			print(b)
			flag = True
			break

if flag == False:
	print('-1')

Submission status: Wrong Answer

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

def f (b, num):
    if num < b:
        return num
    elif num >= b:
        return f(b, int(num / b)) + num % b


ans = -1
if n > s:
    if s == 1:
        ans = n
    elif s < n / 10000:
        for i in range(int(n / 2), n + 1):
    # print f(i, n)
            if f(i, n) == s:
                #  print 'hey'
                ans = i
                break
    else:
        for i in range(2, int(n / 2)):
            # print f(i, n)
            if f(i, n) == s:
                #  print 'hey'
                ans = i
                break     
print ans

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys,copy,math,heapq,itertools as it,fractions,re,bisect,collections as coll

def f(b, n):
    if n < b: return n
    return f(b, n/b) + n%b
    
n = int(raw_input())
s = int(raw_input())

for b in xrange(2, 1000000):
    if f(b, n) == s:
        print b
        break
else:
    if n == s:
        print n + 1
    elif n > s:
        print n - s + 1
    else:
        print -1

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys,copy,math,heapq,itertools as it,fractions,re,bisect,collections as coll

def f(b, n):
    if n < b: return n
    return f(b, n/b) + n%b
    
n = int(raw_input())
s = int(raw_input())

for b in xrange(2, 1000000):
    if f(b, n) == s:
        print b
        break
else:
    if n == s: 
        print n + 1
    else:
        print -1

Submission status: Wrong Answer

Solution code:
import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')

# input macro
def i():
    return int(raw_input())
def ii():
    return map(int,raw_input().split(" "))
def s():
    return raw_input()
def ss():
    return raw_input().split(" ")
def slist():
    return list(raw_input())
#

def join(s):
    return ''.join(s)

#iterate macro
def piter(n,m):
    return itertools.permutations(n,m)
def citer(n,m):
    return itertools.combinations(n,m)

#modulo macro
def modc(a,b,m):
    c = 1
    for i in xrange(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1,m) % m
    return c
 
def gcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
 
def modinv(a, m):
    (inv, q, gcd_val) = gcd(a, m)
    return inv % m

#bisect macro
def index(a, x):
    #Locate the leftmost value exactly equal to x
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

#memoize macro
def memoize(f):
    cache = {}
    def helper(*args):
        if args not in cache:
            cache[(args)] = f(*args)
        return cache[args]
    return helper

@memoize
def nck(a,b,m):
    b = min([a-b,b])
    if (b>a or b<0 or a<0):
        return 0
    elif a == 0:
        return 1
    return (nck(a-1,b-1,m)+nck(a-1,b,m)) % m

nh=zip([1,0,-1,0],[0,1,0,-1])

###########

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

n=i()
s=i()


if n==s:
    print n+1
elif n<s:
    print -1
else:
    for j in range(2,int(math.sqrt(n))+1):
        if (n-s)%(j-1)==0:
            if wa(j,n)==s:
                print j
                break
    else:
        for j in range(1,int(math.sqrt(n))+1):
            if (n-s)%j==0:
                if wa((n-s)/j+1,n)==s:
                    print (n-s)/j+1
                    break
        else:
            print -1

Submission status: Wrong Answer

Solution code:
def read():
    return int(input())

def reads(sep=None):
    return list(map(int, input().split(sep)))

def f(b, n):
	c = 0
	while n:
		if n < b:
			c += n
			break
		else:
			c += n % b
			n //= b
	return c

def main():
	n = read()
	s = read()
	if n < s:
		print(-1)
	elif n == s:
		print(n + 1)
	elif s == 1:
		print(n)
	else:
		b = 2
		while b*b <= n:
			if f(b, n) == s:
				print(b)
				return
			b += 1
		i = 1
		bs = []
		while i*i < n + 1:
			if (n-s)%i != 0:
				bs.append((n-s)%i + 1)
			i += 1
		for b in sorted(bs):
			if f(b, n) == s:
				print(b)
				return
		print(-1)
	
main()

Submission status: Wrong Answer

Solution code:
def read():
    return int(input())

def reads(sep=None):
    return list(map(int, input().split(sep)))

def f(b, n):
	c = 0
	while n:
		if n < b:
			c += n
			break
		else:
			c += n % b
			n //= b
	return c

def main():
	n = read()
	s = read()
	if n < s:
		print(-1)
	elif n == s:
		print(n + 1)
	else:
		b = 2
		while b*b <= n:
			if f(b, n) == s:
				print(b)
				return
			b += 1
		i = 1
		bs = []
		while i*i <= n:
			if (n-s)%i != 0:
				bs.append((n-s)%i + 1)
			i += 1
		for b in sorted(bs):
			if f(b, n) == s:
				print(b)
				return
		print(-1)
	
main()

Submission status: Wrong Answer

Solution code:
x = int(raw_input())
y = int(raw_input())

def sumdigit(b=x, n=y):
    if n < b:
        return n
    else:
        temp = n / b
        return sumdigit(b, n//b) + n%b

print sumdigit(x, y)

Submission status: Wrong Answer

Solution code:
x = int(raw_input())
y = int(raw_input())

def sumdigit(b=x, n=y):
    if n < b:
        return n
    else:
        temp = n / b
        print temp
        return sumdigit(b, n//b) + n%b

print sumdigit(x, y)

Submission status: Wrong Answer

Solution code:
x = int(raw_input())
y = int(raw_input())
def sumdigit(b=x, n=y):
    if n < b:
        return n
    else:
        return sumdigit(b, n/b) + n%b

print sumdigit(x, y)

Submission status: Wrong Answer

Solution code:
class nnDigitSum:
	def dfs(self,b,n):
		if n<b:
			return n
		return self.dfs(b,n/b)+n%b
	def returnMinimumB(self,n,s):
		if n<s: return -1
		if n==s: return n+1
		if s==1: return n
		i=2
		while i*i<=n:
			if self.dfs(i,n)==s: return i
			i+=1
		cands=[]
		i=1
		while i*i<=n-2:
			if not (n-s)%i: cands.append((n-s)/i+1)
			i+=1
		cands=sorted(cands)
		for cand in cands:
			if self.dfs(cand,n)==s: return cand
		return -1
if __name__ == "__main__":
	N = int(raw_input())
	s = int(raw_input())
	d = nnDigitSum()
	print d.returnMinimumB(N,s)

Submission status: Wrong Answer

Solution code:
class nnDigitSum:
	def dfs(self,b,n):
		if n<b:
			return n
		return self.dfs(b,n/b)+n%b
	def returnMinimumB(self,n,s):
		i=2
		while i*i>=n:
			if self.dfs(i,n)==s: return i
			i-=1
		cands=[]
		i=1
		while i*i<=n-2:
			if not (n-s)%i: cands.append((n-s)/i+1)
			i+=1
		cands=sorted(cands)
		for cand in cands:
			if self.dfs(cand,n)==s: return cand
		if n==s:
			return n+1
		return -1
if __name__ == "__main__":
	N = int(raw_input())
	s = int(raw_input())
	d = nnDigitSum()
	print d.returnMinimumB(N,s)

Submission status: Wrong Answer

Solution code:
class nnDigitSum:
	def dfs(self,b,n):
		if n<b:
			return n
		return self.dfs(b,n/b)+n%b
	def returnMinimumB(self,n,s):
		i=2
		while i*i<=n:
			if self.dfs(i,n)==s: return i
			i+=1
		cands=[]
		i=1
		while i*i<=n-2:
			if not (n-s)%i: cands.append((n-s)/i+1)
			i+=1
		cands=sorted(cands)
		for cand in cands:
			if self.dfs(cand,n)==s: return cand
		if n==s:
			return n+1
		return -1
if __name__ == "__main__":
	N = int(raw_input())
	s = int(raw_input())
	d = nnDigitSum()
	print d.returnMinimumB(N,s)

Submission status: Wrong Answer

Solution code:
class DigitSum:
	def dfs(self,b,n):
		if n<b:
			return n
		return self.dfs(b,n/b)+n%b
	def returnMinimumB(self,N,s):
		for b in range(2,10**len(str(N))):
			print self.dfs(b,N),b
			if s == self.dfs(b,N):
				if N<b:
					if N==s:
						print N
					else:
						print -1 
					return
				print b
				return
		print -1

if __name__ == "__main__":
	N = int(raw_input())
	s = int(raw_input())
	d = DigitSum()
	d.returnMinimumB(N,s)

Submission status: Wrong Answer

Solution code:
class DigitSum:
	def dfs(self,b,n):
		if n<b:
			return n
		return self.dfs(b,n/b)+n%b
	def returnMinimumB(self,N,s):
		for b in range(2,10*len(str(N))):
			if s != self.dfs(b,N):
				continue
			else:
				if N<b:
					if N==s:
						print n
					else:
						print -1 
					return
				print b
				return
		print -1

if __name__ == "__main__":
	N = int(raw_input())
	s = int(raw_input())
	d = DigitSum()
	d.returnMinimumB(N,s)

Submission status: Wrong Answer

Solution code:
class DigitSum:
	def dfs(self,b,n):
		if n<b:
			return n
		return self.dfs(b,n/b)+n%b
	def returnMinimumB(self,N,s):
		if s == 1:
			print N
			return
		for b in range(2,10*len(str(N))):
			if s != self.dfs(b,N):
				continue
			else:
				if N<b:
					if N==s:
						print n
					else:
						print -1 
					return
				print b
				return
		print -1

if __name__ == "__main__":
	N = int(raw_input())
	s = int(raw_input())
	d = DigitSum()
	d.returnMinimumB(N,s)

Submission status: Wrong Answer

Solution code:
class DigitSum:
	def dfs(self,b,n):
		if n<b:
			return n
		return self.dfs(b,n/b)+n%b
	def returnMinimumB(self,N,s):
		if s == 1:
			print N
			return
		for b in range(2,100+1):
			if s != self.dfs(b,N):
				continue
			else:
				if N<b:
					if N==s:
						print n
					else:
						print -1 
					return
				print b
				return
		print -1

if __name__ == "__main__":
	N = int(raw_input())
	s = int(raw_input())
	d = DigitSum()
	d.returnMinimumB(N,s)

Submission status: Wrong Answer

Solution code:

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

import math

n = input()
s = input()
d = n-s
if d < 0:
	print -1
elif d == 0:
	print n + 1
else:
	ans = 9876653123122323223223232
	for i in range(1, int(math.sqrt(d))+2):
		if d % i == 0:
			# print i
			if solve(n, i+1, s): 
				ans = min(ans, i+1)
			if solve(n, d/i, s):
				ans = min(ans, d/i + 1)
	if ans == 9876653123122323223223232:
		print -1
	else: print ans

Submission status: Wrong Answer

Solution code:

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

import math

n = input()
s = input()
d = n-s
if d < 0:
	print -1
elif d == 0:
	print n + 1
else:
	ans = 98766531231223232232
	for i in range(1, int(math.sqrt(d))+1):
		if d % i == 0:
			# print i
			if solve(n, i+1, s): 
				ans = min(ans, i+1)
			if solve(n, d/i, s):
				ans = min(ans, d/i + 1)
	if ans == 98766531231223232232:
		print -1
	else: print ans

Submission status: Wrong Answer

Solution code:

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

import math

n = input()
s = input()
if s > n:
	print -1
elif s == n:
	print n+1
else:
	d = n-s
	if d < 0:
		print -1
	if d > s:
		print n
	else:
		ans = 987665312312
		for i in range(2, int(math.sqrt(d))+1):
			if d % i == 0:
				# print i
				if solve(n, i+1, s): 
					ans = min(ans, i+1)
				if solve(n, d/i, s):
					ans = min(ans, d/i + 1)
		if ans == 987665312312:
			print -1
		else: print ans

Submission status: Wrong Answer

Solution code:
import sys


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


def main():
    n = int(raw_input())
    s = int(raw_input())
    if s == n:
        print n+1
    else:
        for b in xrange(2, int(n**(1./2))+1):
            if calc(b, n) == s:
                print b
                exit()
        for b in xrange(1, int(n**(1./2))+1):
            a = (n-s)/b + 1
            if calc(a, n) == s:
                print a
                exit()
        print -1


if __name__ == "__main__":
    # sys.setrecursionlimit(100*10000)
    main()

Submission status: Wrong Answer

Solution code:
import sys

lim = sys.getrecursionlimit()
sys.setrecursionlimit(lim)

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

n, s= [int(input()) for i in range(2)]
ans = -1
for b in range(2, s+1):
    if s == f(b, n):
        ans = b
        break
if s == 1:
    print(n)
else:
    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, int(n / b)) + n % b


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


for p in range(1,1000000):
    q = s -p
    b = (n-q)//p  
    if (n-q)%p:continue
    else:
        #f(b,n)==s
        print(b)
        exit(0)

print(-1)

Submission status: Wrong Answer

Solution code:
n,s,flag = int(input()),int(input()),0

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

for i in range(2,n+1):
    if function(i,n) == s:
        print(i)
        flag = 1
        break

if flag == 0:
    print("-1")

Submission status: Wrong Answer

Solution code:
import math

n, s = [int(input()) for i in range(2)]
res = 0

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

for b in range(n + 1):
    if b < 2:
        continue
    elif f(b, n) == s:
        res = b
        break
    else:
        continue

print(res if res > 0 else '-1')

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, int(n / b)) + n % b


for i in range(2,1000000):
    if f(i, n) == s:
        print(i)
        break

else:
    #b > 10^6
    # f(b,n)=int(n / b) + n % b
    i=10**6
    while i<= 10**21:
        x = f(i, n)
        if x==s:
            print(i)
            exit(0)
        if x >s:
            i+= x-s
        if x<s:
            print(-1)
            exit(0)