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:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

#n = int(input())
#n,a = [int(i) for i in readline().split()]
n = int(input())
s = int(input())

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


c = int(n**0.5)+2
for b in range(2,c):
    if digit_sum(n,b) == s:
        print(b)
        exit()

for p in range(c,0,-1):
    q = s-p
    if q < 0: continue
    if (n-q)%p: continue
    b = (n-q)//p
    if p >= b: continue
    if q >= b: continue
    
    print(b)
    exit()
if n==s:
    print(n+1)
    exit()


print(-1)

Submission status: Accepted

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

b_ans=1



if n==s:
  b_ans=n+1
if b_ans==1:
  for b in range(2,int(n**0.5)+1):
    nn=n
    st=[]
    while(nn>0):
      st.append(nn%b)
      nn=(nn-st[-1])/b
  
    if sum(st)==s:
      b_ans=b
      break

if b_ans==1:
  for p in range(int(n**0.5),0,-1):
    b=(n-s+p)/p

    if b.is_integer() and 0<=s-p<b and b>n**0.5:
      b_ans=int(b)
      break

if b_ans!=1:
  print(b_ans)
else:
  print(-1)

Submission status: Accepted

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

    if N == S:
        print(N + 1)
        return

    def digitSum(n, b):
        if b < 2:
            return -1
        if n < b:
            return n
        return digitSum(n // b, b) + n % b

    for b in range(2, int(N**0.5) + 1):
        if digitSum(N, b) == S:
            print(b)
            return

    for p in range(int(N**0.5), 0, -1):
        b = (N - S) // p + 1
        if digitSum(N, b) == S:
            print(b)
            return
    print('-1')

sol()

Submission status: Accepted

Solution code:
import math
import sys
import functools

sys.setrecursionlimit(10 ** 9)

@functools.lru_cache(None)
def f(b, n):
    if n < b:
        return n
    else:
        return f(b, n // b) + (n % b)

def main(n, s):
    if s == n:
        return n + 1

    if s > n:
        return -1

    for b in range(2, math.ceil(math.sqrt(n)) + 1):
        if f(b, n) == s:
            return b

    ans = float('inf')
    for p in range(1, math.ceil(math.sqrt(n)) + 1):
        if (n - s) % p == 0:
            b = (n - s) // p + 1
            if f(b, n) == s:
                ans = min(ans, b)

    return -1 if ans == float('inf') else ans

if __name__ == '__main__':
    n = int(input())
    s = int(input())
    print(main(n, s))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n = II()
    k = II()
    x = II()
    y = II()
    ans = 0
    for i in range(n):
        if i >= k:
            ans += y
        else:
            ans += x
    print(ans)
    return

#B
def B():
    w = S()
    d = defaultdict(int)
    for s in w:
        d[s] += 1
    for di in d.values():
        if di % 2:
            print("No")
            return
    print("Yes")
    return

#C
def C():
    n, a = LI()
    x = LI()
    sumx = [0] * n
    for i in range(n):
        sumx[i] = sumx[i - 1] + x[i]
    dp = [[[0] * (n+1) for i in range(sumx[-1] + 1)] for i in range(n)]
    for i in range(n):
        dp[i][x[i]][1] = 1
    for i in range(1, n):
        for s in range(sumx[i] + 1):
            for k in range(1, i + 2):
                if  s >= x[i]:
                    dp[i][s][k] += dp[i - 1][s - x[i]][k - 1]
                dp[i][s][k] += dp[i - 1][s][k]
    ans = 0
    for i in range(1, n + 1):
        if a * i > sumx[-1]:
            break
        ans += dp[-1][a * i][i]
    print(ans)
    return

# D
# 解説AC
# 2 <= b <= √n
# までに関しては全探索すればよくて
# ここで解がない場合はそれ以上を見る 
# √n < b <= n
# に関してはb進数表記で2桁になることが確定してて
# n = p*b+qとするなら p + q = s で(1 <= p < b, 0 <= q < b)
# n = p*b+q >= p*b > p**2 → √n > p がわかるからpを全探索
# b = (n-s)/p + 1なのでpを決めればbが決まってあとは調べればいい
# 数学じゃんこれ！ 
def D():
    def f(b, n):
        if n < b:
            return n
        return f(b, n // b) + (n % b)
    n, s = IR(2)
    if n == s:
        print(n + 1)
        return
    for b in range(2, int(math.sqrt(n)) + 1):
        if s == f(b, n):
            print(b)
            return
    for p in range(int(math.sqrt(n)), 0, -1):
        b = (n - s) // p + 1
        if b <= 1:
            continue
        if s == f(b, n):
            print(b)
            return
    print(-1)
    return


#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

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

n,s = [int(input()) for _ in [0]*2]
b = -1
if n==s:b=n+1
else:
    for i in range(2,int(n**0.5)+1):
        if f(i,n)==s:
            b = i
            break
    else:
        for i in range(int(n**0.5),0,-1):
            j = (n-s)//i + 1
            if f(j,n)==s:
                b = j
                break
print(b)

Submission status: Accepted

Solution code:

import sys


def check(num, s, b):
    sum_keta = 0
    while num > 0:
        sum_keta += num % b
        num //= b
    if sum_keta == s:
        return 1
    else:
        return 0


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

    if num < s:
        print(-1)
        sys.exit()

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

    if num == 1:
        print(-1)
        sys.exit()

    for b in range(2, int(num ** 0.5) + 2):
        if check(num, s, b):
            print(b)
            sys.exit()

    for p in range(1, int(num ** 0.5) + 2)[::-1]:
        b = (num - s) // p + 1
        if b <= 1:
            continue
        if check(num, s, b):
            print(b)
            sys.exit()

    print(-1)






if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import ceil
from itertools import permutations

#S=input()
#D=list(map(int,input().split()))
from heapq import *
"""
import sys
input=sys.stdin.readline
"""
from collections import defaultdict
from fractions import gcd
#S=
from math import sqrt
import sys
sys.setrecursionlimit(100100)

from collections import deque
import bisect
import sys
input=sys.stdin.readline

n=int(input())
s=int(input())
if s>n:
    print(-1)
    quit()
if s==n :
    print(n+1)
    quit()
def func(b,n):
    res=0
    while(n):
        res+=n%b
        n//=b
    return res
j=1
i=n
ans=10**30
for i in range(2,int(sqrt(n))+1):
    if func(i,n)==s:
        ans=min(ans,i)
l=defaultdict()
for i in range(1,ceil(sqrt(n))):
    b=(n-s)//i+1
    if sqrt(n)<b and n//b+(n%b)==s:
        ans=min(ans,b)
if ans==10**30:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

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

def solve(n, s) :
    if n == s :
        return n + 1
    if s > n :
        return -1
    
    b = 2
    while b * b <= n :
        if f(b, n) == s :
            return b
        b += 1
            
    p = int(-(-(n ** 0.5 - 1) // 1))
    while p > 0 :
        if (n - s) % p == 0 :
            b = 1 + (n - s) // p
            if p < b and 0 <= s - p < b :
                return b
            
        p -= 1
        
    return -1
            
print(solve(n, s))

Submission status: Accepted

Solution code:
import math
import os
import sys
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, S = [int(sys.stdin.readline()) for _ in range(2)]


@lru_cache(maxsize=None)
def f(b, n):
    if n < b:
        return n
    return f(b, int(n // b)) + n % b


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

# #########
# b = 2
# ans = -1
# prev = 0
# while b <= N:
#     if f(b, N) > prev:
#         print(b, N, f(b, N))
#     prev = f(b, N)
#     b += 1
# ##########

b = 2
ans = -1
while b <= math.sqrt(N) + 1:
    if f(b, N) == S:
        ans = b
        break
    b += 1
if ans >= 0:
    print(ans)
    exit()

ans = INF
# b > sqrt(N) のとき 2 桁になるので上位桁を全探索する
for d2 in range(1, int(math.sqrt(N)) + 1):
    if (N - S) % d2 == 0:
        b = int(1 + (N - S) // d2)
        if b >= 2 and f(b, N) == S:
            ans = min(ans, b)
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import math
import sys
sys.setrecursionlimit(10**5)
n = int(input())
s = int(input())

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

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

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

if n == 1:
    print (-1)
    exit()

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

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

# for i in range(2, 100):
#     print (i, f(i,100))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)

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

n=int(input())
s=int(input())
if s>n:
  print(-1)
elif s==n:
  print(n+1)
else:
  ans=10**18
  for i in range(2,int(n**0.5)+1):
    if f(i,n)==s:
      ans=i
      break
  if ans!=10**18:
    print(ans)
  else:
    for i in range(1,int(n**0.5)+1):
      tb=(n-s)//i+1
      if tb==1:
        continue
      if f(tb,n)==s:
        ans=min(ans,tb)
    if ans!=10**18:
      print(ans)
    else:
      print(-1)

Submission status: Accepted

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

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


def solve(n,s):
  if s > n:
    return -1
  if s == n:
    return n+1
  nsq = int(n**0.5 + 1)
  for b in range(2,nsq+1):
    if f(b,n) == s:
      return b
  # 2桁で作れるかどうか
  # n = bx+y, s = x+y, x,y < b
  # n - s = (b-1)x, x < b
  m = n-s
  msq = int(m**0.5+1)
  for x in range(msq,0,-1):
    if m%x:
      continue
    b = m//x+1
    if f(b,n) == s:
      return b
  return -1
  
answer = solve(n,s)
print(answer)

Submission status: Accepted

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

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

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

for k in range(2,math.floor(math.sqrt(n))+2):
    if f(k,n) == s:
        print(k)
        exit(0)

P = [1,n-s]
for k in range(2,math.floor(math.sqrt(n-s))+1):
    if (n-s) % k == 0:
        P.append(k)
        P.append((n-s)//k)

P = sorted([p+1 for p in P])
for b in P:
    if f(b,n) == s:
        print(b)
        exit(0)
print(-1)

Submission status: Accepted

Solution code:
import math


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())
    if s == n:
        print(n+1)
        return
    elif s > n:
        print(-1)
        return
    sqrt = int(math.sqrt(n))
    for b in range(2, sqrt+2):
        if f(b, n) == s:
            print(b)
            return
    for x in range(sqrt, 0, -1):
        if x > s:
            continue
        y = s - x
        b = (n - y) // x
        if b >= 2 and (n - y) % x == 0 and f(b, n) == s:
            print(b)
            return
    print(-1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
	n = int(input())
	s = int(input())
	ans = solve(n, s)
	print(ans)

def solve(n: int, s: int) -> int:
	if n == s:
		return n+1

	def f(b:int, n:int) -> int:
		if b < 2:
			return -1
		if b > n:
			return n
		cur = n
		ans = 0
		while cur > 0:
			ans += cur%b
			cur //= b
		return ans

	sqrtn = int(n**0.5)
	for i in range(2, sqrtn):
		this_ans = f(i, n)
		if this_ans == s:
			return i

	for p in range(sqrtn+1, 0, -1):
		if (n-s)%p != 0:
			continue
		b = (n-s)//p + 1
		if f(b, n) == s:
			return b
	return -1


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys

def f(b, n):
    if b < 2:
        return -1    

    if b > n:
        return n

    return f(b, n//b) + n % b


def main():
    input = sys.stdin.readline
    n = int(input())
    s = int(input())

    if s > n:
        return -1

    if s == n:
        return n+1

    for i in range(2, int(n**0.5)):
        if f(i, n) == s:
            return i

    for p in range(int(n**0.5) + 1, 0, -1):
        if (n - s) % p != 0:
            continue

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

    return -1


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
import math


def f(b: int, n: int) -> int:
    if b > n:
        return n
    return f(b, n // b) + (n % b)


def digit_sum(n: int, s: int) -> int:
    if n == s:
        return n + 1

    sqrt = math.sqrt(n)
    sqrt = math.ceil(sqrt)

    for b in range(2, sqrt + 1):
        if f(b, n) == s:
            return b

    for p in range(sqrt, 0, -1):
        if (n - s) % p:
            continue

        b = (n - s) // p + 1

        if b < 2:
            continue

        if f(b, n) == s:
            return b

    return -1


if __name__ == "__main__":
    n = int(input())
    s = int(input())
    ans = digit_sum(n, s)
    print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
sys.setrecursionlimit(10000)
input = stdin.readline

n = int(input().rstrip())
s = int(input().rstrip())

def f(b, n):
	if n < b:
		return n
	else:
		return f(b, int(n/b)) + (n % b)
if s == n:
	print(n+1)
else:
	for i in range(2, int(n**(1/2))+1):
		if f(i, n) == s:
			print(i)
			break
	else:
		for p in range(int(n**(1/2)), 0, -1):
			if (n-s) % p == 0:
				b = (n-s)/p + 1
				if b >= 2 and f(b, n) == s:
					print(int(b))
					break
			else:
				continue
		else:
			print(-1)

Submission status: Accepted

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

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

ans=-1
if s==n:
	ans=n+1
else:
	for _b in range(2,int(n**0.5)+1):
		if f(_b,n)==s:
			ans=_b
			break
	if ans==-1:
		for _p in range(int(n**0.5),0,-1):
			_b = (n-s)//_p+1
			if f(_b,n)==s:
				ans=_b
				break
print(ans)

Submission status: Accepted

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

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

m = int(n ** 0.5) + 1

for b in range(2, m + 1):
    temp = n
    t = 0
    while temp >= b:
        t += temp % b
        temp //= b
    if s == t + temp:
        print(b)
        exit()

for p in range(m, 0, -1):
    if (n - s) % p != 0:
        continue
    b = (n - s) // p + 1
    temp = n
    t = 0
    while temp >= b:
        t += temp % b
        temp //= b
    if s == t + temp:
        print(b)
        exit()

print(-1)

Submission status: Accepted

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

#A

#B

#C
"""
n,a = LI()
x = LI()
s = sum(x)
dp = [[[0 for i in range(s+1)] for j in range(n+1)] for k in range(n+1)]
for i in range(n+1):
    dp[i][0][0] = 1
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(s+1):
            if k >= x[i-1]:
                dp[i][j][k] = dp[i-1][j][k]+dp[i-1][j-1][k-x[i-1]]
            else:
                dp[i][j][k] = dp[i-1][j][k]
ans = 0
for i in range(1,n+1):
    if a*i <= s:
        ans += dp[n][i][a*i]
print(ans)
"""

#D
def f(b,n):
    m = n
    res = 0
    while m > 0:
        res += m%b
        m //= b
    return res
n,s = IR(2)
if n == s:
    print(n+1)
    quit()
if n == 1:
    print(-1)
    quit()
k = int(n**0.5)
for b in range(2,k+1):
    if f(b,n) == s:
        print(b)
        quit()
for p in range(1,k+1)[::-1]:
    if (n-s)%p == 0:
        b = (n-s)//p+1
        if b != 0:
            if f(b,n) == s:
                print(b)
                quit()
print(-1)

#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Accepted

Solution code:
#ABC044D
def fun(b,n):
    if b<2:return -1
    if n<b:return n
    return (n%b)+fun(b,n//b)
n=int(input())
s=int(input())
n_root=n**0.5

def main(n,n_root,s):
    if s==n:return n+1
    if s>n:return -1
    for b in range(2,1+int(n_root)):
        if fun(b,n)==s:
            return b
    for i in range(int(n_root),0,-1):
        b=1+(n-s)//i
        if fun(b,n)==s:
            if b>1:return b
    return -1
print(main(n,n_root,s))

Submission status: Accepted

Solution code:
#ABC044D
def fun(b,n):
    if n<b:return n
    return (n%b)+fun(b,n//b)
n=int(input())
s=int(input())
n_root=n**0.5

def main(n,n_root,s):
    if s==n:return n+1
    if s>n:return -1
    if (n//2)+1<s:return -1
    for b in range(2,1+int(n_root)):
        if fun(b,n)==s:
            return b
    for i in range(int(n_root),0,-1):
        b=1+(n-s)//i
        if fun(b,n)==s:
            if b>1:return b
    return -1
print(main(n,n_root,s))

Submission status: Accepted

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

flag = False
if s > n or (n//2)+1<s<n:
  print(-1)
  exit()
  
if s == n:
  print(n+1)
  exit()

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

for b in range(2, int(n**0.5)+1):
  if chk(b, n) == s:
    print(b)
    flag = True
    exit()

for i in range(int(n**0.5), 0, -1):
  b = (n-s)//i + 1
  if chk(b, n) == s:
    if b > 1:
      print(b)
      flag = True
      exit()

if flag == False:
  print(-1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

"""
・参考：http://arc060.contest.atcoder.jp/data/arc/060/editorial.pdf
　　　　https://www.youtube.com/watch?v=LzxPxJ-cSHk
・b <= √nは愚直に当たっていく。
・b > √nは、b^2 > nなので、b進数で2桁以下になる。
　例) 10^2は10進数で100、100 > n → nは99以下
　その2桁の数字はn = p*b + qと表せる。
　例) 67 = 6*10 + 7
　今回の問題の条件から、s = p + q
　n = p*b + q
　s = p + q
　上記2つの式から、連立方程式でqを消すと、
　n-s = p*b - p
　と表せる。
　pはb以上なら桁が上がってしまうので p < b
　p < b から p*p < p*b なので、p*b > p^2
　よって、n = p*b + q >= p*b > p^2
　n > p^2 なので、√n > p
　つまりpについて√nまでを全探索すればOK。
　n-s = p*b - p をbについての形に変形すればbが出せる。
　b = (n-s)/p + 1
"""

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

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

n = INT()
s = INT()

if s > n:
    print(-1)
elif s == n:
    print(n+1)
elif ceil(n/2) < s < n:
    print(-1)
else:
    # b <= √n の全探索
    for b in range(2, int(sqrt(n))+2):
        if f(b, n) == s:
            print(b)
            exit()
    # b > √n について、式を元に探す
    # pが大きい程bが小さいので、このループは逆順で回す
    for p in range(int(sqrt(n))+2, 0, -1):
        # 整数にならないものは除外
        if (n-s)%p: continue
        b = (n-s)//p + 1
        if f(b, n) == s:
            print(b)
            exit()
    # 見つからなかった
    print(-1)

Submission status: Accepted

Solution code:
def f(b, n):
  return n % b + f(b, n // b) if n > 0 else 0
n = int(input())
s = int(input())
for i in range(2, 5**8):
  if f(i, n) == s:
    print(i)
    exit()
for i in range(n - s >> 18, 0, -1):
  if f((n - s) // i + 1, n) == s:
    print((n - s) // i + 1)
    exit()
print(n + 1 if n == s else -1)

Submission status: Accepted

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

# コーナーケース
if N == S:
    print(N + 1)
    exit()


# x進数
def encode_x_base(n, x):
    ret = []
    while n:
        ret.append(n % x)
        n //= x
    return ret[::-1]


# 桁和
def digit_sum(n):
    if isinstance(n, (int, str)):
        return sum([int(d) for d in str(n)])
    if isinstance(n, list):
        return sum([int(d) for d in n])


# Bが小さいとき
for b in range(2, int(N ** 0.5) + 1):
    encoded_N = encode_x_base(N, b)
    d_sum = digit_sum(encoded_N)
    if d_sum == S:
        print(b)
        exit()

# Bが大きいときはpを全探索
for p in range(int(N ** 0.5) + 1, 0, -1):
    b = (N - S) // p + 1
    if b < 2:
        continue
    encoded_N = encode_x_base(N, b)
    d_sum = digit_sum(encoded_N)
    if d_sum == S:
        print(b)
        break
else:
    print(-1)

Submission status: Accepted

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

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

ans = -1
if S==N:
    ans = N+1
else:
    for b in range(2,int(N**.5)+1):
        if f(b,N)==S:
            ans = b
            break

if ans == -1:
    for i in range(int(N**.5)+1,0,-1):
        b = (N-S)//i + 1
        if b>1:
            if f(b,N)==S:
                ans = b
                break

print(ans)

Submission status: Accepted

Solution code:
import math

def digitsum(x, b):
    accum = 0
    while x > 0:
        accum += x % b
        x //= b
    return accum

def solve(n, s, max_ns):
    if n < s: return -1
    # 1 <= n < 2**37
    max_digits = int(math.ceil(math.log2(max_ns)))
    # sentinel.
    min_b = n + 2

    # 1桁
    if n == s:
         min_b = n + 1

    # 2桁
    # 10*11程度調べるのは重すぎる
    # それぞれの数字0<=x,y<=b-1として
    # xb + y = n, x + y = s
    # => x(b-1) = n-s
    # 2 .. (n-s)^(1/2) の範囲で約数qを持てば、b=q+1またはb=(n-s)//q+1が候補
    for q in range(1, int((n - s)**0.5) + 1):
        if (n - s) % q == 0:
            for b in [q + 1, (n - s) // q + 1]:
                if b < min_b:
                    if digitsum(n, b) == s:
                        min_b = b

    # 3桁以上
    # <=> n >= b**(3 - 1)
    # <=> b <= n**(1/2)
    b_low = 2
    b_high = min(min_b, int(n ** 0.5) + 1)
    for b in range(b_low, b_high):
        if digitsum(n, b) == s:
            min_b = b

    if min_b < n + 2:
        return min_b
    return -1

def test():
    import random
    random.seed(0)
    for i in range(100):
        b = random.randint(2, 10**11)
        n = random.randint(1, 10**11)
        s = digitsum(n, b)
        solved_b = solve(n, s, 10**11)
        if s == digitsum(n, solved_b) and solved_b <= b:
            print('OK b={}, n={}, s={}, solved_b={}'.format(b, n, s, solved_b))
        else:
            print('NG!!! b={}, n={}, s={}, solved_b={}'.format(b, n, s, solved_b))

if __name__ == '__main__':
    n = int(input())
    s = int(input())
    print(solve(n, s, 10**11))

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 math
n, s = [int(input()) for _ in range(2)]


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 i in range(2, int(math.sqrt(n)) + 1):
    if f(i, n) == s:
        print(i)
        exit()

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

print(-1)

Submission status: Accepted

Solution code:
import math
import sys

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

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

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

for i in range(2,int(math.sqrt(n))+5):
    if digsum(i,n)==s:
        print(i)
        sys.exit()

for i in range(int(math.sqrt(n)),0,-1):

    if s-i>=0 and n-(s-i)>=0 and (n-(s-i))%i==0 and (n-(s-i))//i>s-i:
        print((n-(s-i))//i)
        sys.exit()

print(-1)

Submission status: Accepted

Solution code:
import math

def gcd(a,b):
    """Compute the greatest common divisor of a and b"""
    while b > 0:
        a, b = b, a % b
    return a
 
def lcm(a, b):
    """Compute the lowest common multiple of a and b"""
    return a * b / gcd(a, b)
 

def f(b,n):
	if n < b:
		return n
	return f(b, n//b) + n%b
 
N = int(input())
S = int(input())

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

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

for B in range(2, int(math.sqrt(N))+1):
	if(f(B,N)==S):
		print(B)
		exit()


for p in range(int(math.sqrt(N))+1, 0, -1):
	B = (N-S)/p + 1
	if(B==int(B) and f(int(B),N)==S):
		print(int(B))
		exit()


print(-1)

Submission status: Accepted

Solution code:
n = int(input())
s = int(input())
d = 0
k = 1
while k*k <= n-s:
  if (n-s)%k > 0:
    k += 1
    continue
  l = (n-s)//k
  if (l+1)*(l+1) > n:
    b = l+1
    if n//b + n%b == s:
      d = b
  b = k+1
  a = 0
  r = n
  while r > 0:
    a += r%b
    r = r//b
  if a == s:
    print(b)
    exit()
  k += 1
if n == s:
  print(n+1)
elif d>0:
  print(d)
else:
  print(-1)

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()
elif N < S:
    print(-1)
    exit()

num = -1
for i in range(2, int(N ** 0.5) + 1):
    if f(i, N) == S:
        num = i
        break


if num == -1:
    for i in range(int(N ** 0.5) + 1, 0, -1):
        if (N - S) % i == 0:
            b = (N - S) // i + 1
            if f(b, N) == S:
                num = b
                break

print(num)

Submission status: Accepted

Solution code:
def f(b, n):
    if n < b:
        return n
    elif n >= b:
        return f(b, n//b) + (n % b)

n, s = [int(input()) for _ in range(2)]
if s == n:
    ans = n+1
elif n < s:
    ans = -1
else:
    ans = -1
    for i in range(2, int(n**0.5)+1):
        if f(i, n) == s:
            ans = i
            break
    if ans == -1:
        for i in range(int(n**0.5), 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:
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()

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

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