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: Accepted

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(N)) + 1):
        if t % i == 0:
            bs.add(i + 1)
            bs.add((t // i) + 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: Accepted

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

def f(b, n):
    ans = 0
    while b <= n:
        ans += n%b
        n //= b
    ans += n
    return ans

if n == s:
    print(n+1)
elif n < s:
    print(-1)
else:
    limit = math.ceil(math.sqrt(n))
    for b in range(2, limit + 1):
        if f(b, n) == s:
            print(b)
            break
    else:
        for p in range(limit, 0 ,-1):
            if s - p >= 0 and n-s+p > 0 and (n-s+p)//p > limit:
                b = (n-s+p)//p
                if f(b, n) == s:
                    print(b)
                    break
        else:
            print(-1)

Submission status: Accepted

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 = 0
  while b:
    a +=b%i
    b//=i
  if s == a:
    print(i)
    exit()
for i in range(ru,0,-1):
  q = s-i
  if q <0:
    continue
  c = (n-q)// i
  if c <= ru-1:
    continue
  b = n+0
  a = 0
  while b:
    a+=b%c
    b//=c
  if a == s:
    print(c)
    exit()
print(-1)

Submission status: Accepted

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: Accepted

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 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: Accepted

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))+1):
        b = (N - S) // p + 1
        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: Accepted

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 - 1, 0, -1):
        q = s - p
        x = n - q
        b = x // p
        if g(b) == s:
            return b
    return -1
    
print(f())

Submission status: Accepted

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 s > n:
        print(-1)
        return
    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: Accepted

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:
    if i*i >= n:
        break
    q, m = divmod(n-(s-i), i)
    if i > q:
        break
    if s-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: Accepted

Solution code:
from math import sqrt
n = int(input())
s = int(input())
def f(x,y):
	if y<x: return y
	else: return f(x,y//x)+(y%x)
if s==n: ans = n+1
elif n<s: ans = -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: Accepted

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+2):
    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: Accepted

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:
    if s == n: f = n + 1
    elif s <= (n + 1) // 2: f = n - s + 1
    elif s == 1: f = n
if f is None: print(-1)
else: print(f)

Submission status: Accepted

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)
l.sort()

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: Accepted

Solution code:
# seishin.py
from math import sqrt
n, s = map(int, open(0).read().split())

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

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

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

# sqrt(n) <= b <= n
for p in range(int(sqrt(n)), 0, -1):
    if (n - s) % p > 0:
        continue
    b = (n - s) // p + 1
    if b*b <= n:
        continue
    if f(b, n) == s:
        print(b)
        exit(0)
print(-1)

Submission status: Accepted

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:
        b = (n - s) // i + 1
        if f(b, n) == s:
            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: Accepted

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(sn, 0, -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: Accepted

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)

ans = n + 1
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:
            ans = min((ans, b))
if s == n:
    print(n+1)
elif ans < n + 1:
    print(ans)
else:
    print(-1)

Submission status: Accepted

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

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

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

res = -1

for p in range(int(sqrt(n)), 0, -1):
  b = (n-s)//p + 1
  if b == 1:
    continue
  if f(b, n) == s:
    res = b
    break

for b in range(2, int(sqrt(n))+2):
  if f(b, n) == s:
    res = b
    break

print(res)

Submission status: Accepted

Solution code:
from math import floor, sqrt
INF = 10 ** 20


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


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

    ans = INF
    # 1桁
    if n == s:
        ans = min(ans, n + 1)

    # 2桁
    for p in range(1, int(sqrt(n)) + 1):
        q = s - p
        b = (n - q) // p
        if 2 <= b and f(b, n) == s:
            ans = min(ans, b)

    # 3桁以上
    for b in range(2, int(sqrt(n)) + 1):
        if f(b, n) == s:
            ans = min(ans, b)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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
    b = (n - q) // p
    if b >= 2 and f(b, n) == s:
        print(b)
        exit()

print(-1)

Submission status: Accepted

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

print("-1")

Submission status: Accepted

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 reversed(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: Accepted

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
		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 s==1: return n
		return -1
if __name__ == "__main__":
	N = int(raw_input())
	s = int(raw_input())
	d = nnDigitSum()
	print d.returnMinimumB(N,s)

Submission status: Accepted

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 = 98766531231223232232232329876653123122323223223232
	for i in range(1, int(math.sqrt(d))+2):
		if d % i == 0:
			if solve(n, i+1, s): 
				ans = min(ans, i+1)
			if solve(n, d/i + 1, s):
				ans = min(ans, d/i + 1)
	if ans == 98766531231223232232232329876653123122323223223232:
		print -1
	else: print ans

Submission status: Accepted

Solution code:
#AGC044D
import sys
import math

def ds(n,b):
 s=0
 while n>0:
  s+=n%b
  n/=b
 return s
 
n=int(raw_input())
s=int(raw_input())
if n<s:
 print -1
 sys,exit()
if n==s:
 print n+1
 sys.exit()

i=2
while i*i<=n:
 if ds(n,i)==s:
  print i
  sys,exit()
 i+=1
 
i=int(math.sqrt(n))
while i>0:
 b=(n-s)/i+1
 if b>1 and b>s-i and b>i:
  if ds(n,b)==s:
   print b
   sys,exit()
 i-=1  
print -1

Submission status: Accepted

Solution code:
import math

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

def solver(n, s):
  if n == s:
    print n+1
    return
  elif n < s:
    print "-1"
    return

  lim = int(math.sqrt(n))
  for i in range(2, lim+1):
    if func(i, n) == s:
      print i
      return

  for i in range(lim):
    p = lim - i
    b = (n-s)/p+1
    cut = int(b)
    if b - cut == 0 and b > lim:
      if func(b, n) == s:
        print b
        return

  print "-1"
  return

n = int(raw_input())
s = int(raw_input())
solver(n, s)

Submission status: Runtime Error

Solution code:
#自分の回答
import math
def digit(b, n):
    if n < b:
        return n
    else:
        return digit(b, math.floor(n/b)) + n % b

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

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

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

for i in range(2, int(math.sqrt(n)) + 2):
    if digit(i, n) == s:
        print(i)
        exit()
    else:
        continue

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

Submission status: Runtime Error

Solution code:
#自分の回答
import math
def digit(b, n):
    if n < b:
        return n
    else:
        return digit(b, math.floor(n/b)) + n % b

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

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

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

for i in range(2, int(math.sqrt(n) + 1)):
    if digit(i, n) == s:
        print(i)
        exit()
    else:
        continue

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

Submission status: Runtime Error

Solution code:
import math
def digit(b, n):
    if n < b:
        return n
    else:
        return digit(b, math.floor(n/b)) + n % b

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

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

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

for i in range(2, int(math.sqrt(n))):
    if digit(i, n) == s:
        print(i)
        exit()
    else:
        continue

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

f = lambda b,n:n if n < b else n%b + f(b,n//b)
import math
ans = n+2
for b in range(2,math.ceil(math.sqrt(n))): #O(√n)の全探索
    if f(b,n) == s:
        ans = b; break
else:
    for p in range(math.ceil(math.sqrt(n))): #n=pb+q (b>√n, p+q=s)に基づいたO(√n)の全探索
        q = s-p
        if p > 0: b = (n-q)/p
        else: b = n+1
        if b == int(b) and f(b,n) == s:
           ans = min(ans,int(b))
if ans == n+2: ans = -1
print(ans)

Submission status: Runtime Error

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


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

    if n == s:
        return n + 1
    # elif n < s:
    #     return -1

    for b in range(2, n + 1):
        if b**2 > n:
            break
        if func(b, n) == s:
            return b

    for p in range(1, n + 1):
        if p**2 > n:
            break

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

    return -1


ans = solve()
print(ans)

Submission status: Runtime Error

Solution code:
import math

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

r = 0

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

nn = int(math.sqrt(n)) + 1

for i in range(2, nn):
    nt = n
    st = 0

    while nt > 0:
        st += nt % i
        nt //= i

    if st == s:
        print(i)
        exit()
    
for i in range(nn, 0, -1):
    nt = n
    st = 0

    b = (n - s) // i + 1
    
    st = n % b + n // b

    if st == s:
        print(b)
        exit()

print(-1)

Submission status: Runtime Error

Solution code:
import math

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

r = 0

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

nn = int(math.sqrt(n)) + 1

for i in range(2, nn):
    nt = n
    st = 0

    while nt > 0:
        st += nt % i
        nt //= i

    if st == s:
        print(i)
        exit()
    
for i in range(nn, -1, -1):
    nt = n
    st = 0

    b = (n - s) // i + 1
    
    st = n % b + n // b

    if st == s:
        print(b)
        exit()

print(-1)

Submission status: Runtime Error

Solution code:
import math

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

r = 0

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

nn = int(math.sqrt(n)) + 1    

for i in range(2, nn):
    nt = n
    st = 0

    while nt > 0:
        st += nt % i
        nt //= i

    if st == s:
        print(i)
        exit()
    
for i in range(2, nn):
    nt = n
    st = 0

    tt = (n - s) // (i + 1)
    
    while nt > 0:
        st += nt % tt
        nt //= tt

    if st == s:
        print(tt)
        exit()

print(-1)

Submission status: Runtime Error

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, S = [int(input()), int(input())]


def solve1():
    i = 2
    while i * i <= N:
        s, n = 0, N
        while n > 0:
            s += n % i
            n //= i
        if s == S:
            return i

        i += 1

    return 1 << 60


def solve2():
    i = 1
    ret = 1 << 60
    while i * i <= N:
        b = (N - S) // i + 1
        s, n = 0, N
        while n > 0:
            s += n % b
            n //= b
        if s == S:
            ret = min(ret, b)
        i += 1

    return ret


def solve():
    ret = min(solve1(), solve2())
    return ret if ret != 1 << 60 else -1


print(solve())

Submission status: Runtime Error

Solution code:
import sys
import math

def divlist(n):
   sl=[]
   ll=[]
   for x in range(1,int(math.sqrt(n))+1):
       if n%x==0:
           sl.append(x)
           ll.append(n//x)
   ll.reverse()
   sl.extend(ll)
   return sl

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

def main(n,s):
    if n<s:
        return print(-1)
    elif n==s:
        return prnit(n+1)
    else:
        dl=divlist(n-s)
        for x in dl:
            if s==f(x+1,n):
                return print(x+1)
        return print(-1)

n=int(sys.stdin.readline().strip())
s=int(sys.stdin.readline().strip())

main(n,s)

Submission status: Runtime Error

Solution code:
import sys
import math

n=int(sys.stdin.readline().strip())
s=int(sys.stdin.readline().strip())

def divlist(n):
   sl=[]
   ll=[]
   for x in range(1,int(math.sqrt(n))+1):
       if n%x==0:
           sl.append(x)
           ll.append(n//x)
   ll.reverse()
   sl.extend(ll)
   return sl

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

if n<s:
    print(-1
elif n==s:
    print(n+1)
else:
    dl=divlist(n-s)
    for x in dl:
        if s==f(x+1,n):
            print(x+1)
            sys.exit()
    print(-1)

Submission status: Runtime Error

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

if n==s:
  print(n+1)
  sys.exit(0)

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

for b in range(2,int(n**0.5)+1):
  ss=f(b,n)
  if ss==s:
    print(b)
    sys.exit(0)

#n=pb+q
for p in range(1,int(n**0.5)+1):
  q=s-p
  b=(n-q)//p
  if q<0 or (n-q)%p!=0:
    continue
    
  ss=f(b,n)
  if ss==s:
    print(b)
    sys.exit(0)
    
print(-1)

Submission status: Runtime Error

Solution code:
n = int(input())
s = int(input())
import sys
sys.setrecursionlimit(20000)

import math
def f(b, n):
    # print(b, n)
    if n<b:
        return n
    else:
        x = f(b, n//b) + n%b
        return x
# print(f(100000000000,100000000000))
ans = 0
# if n<s:
#     print(-1)
#     exit()
if n==s:
    print(n+1)
    exit()
for b in range(2,int(math.sqrt(n))+500):
    if f(b, n) == s:
        ans = b
        print(ans)
        exit()
for p in range(int(math.sqrt(n)), 0, -1):
    if (n+p-s) %p == 0:
        # print(p)
        if f((n+p-s)//p, n) == s:
            print((n+p-s)//p)
            exit()


print(-1)

Submission status: Runtime Error

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

import math
def f(b, n):
    # print(b, n)
    if n<b:
        return n
    else:
        
        x = f(b, n//b) + n%b
        return x
ans = 0
if n<s:
    print(-1)
    exit()
for b in range(2,int(math.sqrt(n))+500):
    if f(b, n) == s:
        ans = b
        print(ans)
        exit()
for p in range(int(math.sqrt(n)), 0, -1):
    if (n+p-s) %p == 0:
        # print(p)
        if f((n+p-s)/p, n) == s:
            print((n+p-s)//p)
            exit()


print(-1)

Submission status: Runtime Error

Solution code:
n = int(input())
s = int(input())
sq = n**.5
ans = '-1'

for b in range(2, int(sq)+1):
	sum = 0
	tmp = n
	while tmp//b != 0:
		sum += tmp%b
		tmp //= b
	sum += tmp
	if sum == s:
		ans = b
		break

if ans == '-1':
	for p in range(int(sq), 0, -1):
		b = (n-s+p)/p
		if b % 1 == 0:
			b = int(b)
			q = n%b
			if p+q == s:
				ans = b
				break

print(ans)

Submission status: Runtime Error

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(inout())
t=-1
for i in range(n-2):
  if f(i+2,n)==s:
    t=i+2
    break
print(t)

Submission status: Runtime Error

Solution code:
n = int(input())
s = int(input())
sq = n**.5
ans = '-1'

for b in range(2, int(sq)+1):
	sum = 0
	tmp = n
	while tmp//b != 0:
		sum += tmp%b
		tmp //= b
	sum += tmp
	if sum == s:
		ans = b
		break

if ans == '-1':
	for p in range(int(sq), 0, -1):
		b = (n-s+p)/p
		if b.is_integer():
			b = int(b)
			q = n%b
			if p+q == s:
				ans = b
				break

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
s = int(input())
sq = n**.5
ans = '-1'

for b in range(2, int(sq)+1):
	sum = 0
	tmp = n
	while tmp//b != 0:
		sum += tmp%b
		tmp //= b
	sum += tmp
	if sum == s:
		ans = b
		break

if ans == '-1':
	if sq.is_integer():
		sq -= 1 
	for p in range(int(sq), 0, -1):
		b = (n-s+p)/p
		if b.is_integer():
			b = int(b)
			q = n%b
			if p+q == s:
				ans = b
				break

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
s = int(input())
sq = n**.5
ans = '-1'

for b in range(2, int(sq)+1):
	sum = 0
	tmp = n
	while tmp//b != 0:
		sum += tmp%b
		tmp //= b
	sum += tmp
	if sum == s:
		ans = b
		break

if ans == '-1':
	if sq.is_integer():
		sq -= 1 
	for p in range(int(sq), 0, -1):
		b = (n-s+p)/p
		if b.is_integer():
			sum = 0
			tmp = n
			while tmp//b != 0:
				sum += tmp%b
				tmp //= b
			sum += tmp
			if sum == s:
				ans = int(b)
				break

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
s = int(input())
sq = n**.5
ans = '-1'

for b in range(2, int(sq)+1):
	sum = 0
	tmp = n
	while tmp//b != 0:
		sum += tmp%b
		tmp //= b
	sum += tmp
	if sum == s:
		ans = b
		break

if ans == '-1':
	if sq.is_integer():
		sq -= 1 
	for p in range(int(sq), 0, -1):
		b = int((n-s+p)/p)
		sum = 0
		tmp = n
		while tmp//b != 0:
			sum += tmp%b
			tmp //= b
		sum += tmp
		if sum == s:
			ans = b
			break

print(ans)