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

Solution (Python):


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

Solution (Python):
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())

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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))

Solution (Python):
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)

Solution (Python):
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()



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





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

Solution (Python):

from math import sqrt
n, s = map(int, open(0).read().split())


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

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


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


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)

Solution (Python):
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)

Solution (Python):
def d_DigitSum(N, S):
    if S == N:
        
        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))
    
    for b in range(2, sn + 1):
        if f(b, N) == S:
            return b
    
    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))

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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
    
    if n == s:
        ans = min(ans, n + 1)

    
    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)

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

Solution (Python):
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)

Solution (Python):

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)

Solution (Python):
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, math.floor(math.sqrt(n))+1):
    
    if(f(b, n) == s):
        print(b)
        sys.exit()


for p in range(1, math.floor(math.sqrt(n))+1):
    
    _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")

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

INF = float('inf')


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)


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


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


def index(a, x):
    
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1


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

Solution (Python):
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)

Solution (Python):

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

Solution (Python):

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

Solution (Python):
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)