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 sys

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

n = input()
s = input()

for i in range(2, n - 1):
	if f(i, n) == s:
		print i
		sys.exit()

print -1

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
n = int(raw_input())
s = int(raw_input())

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

for b in xrange(2, n+1):
    if f(b, n) == s:
        print b
        sys.exit()
print -1

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
n = int(raw_input())
s = int(raw_input())

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

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

for b in xrange(2, 65536):
    if f(b, n) == s:
        print b
        sys.exit()
print -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:
    if s==1:
        print(n)
    print(-1)

Submission status: Wrong Answer

Solution code:
import math
N=int(input())
S=int(input())
for b in range(2,N+1):
    keta=int(math.log(N,b))
    ans=0
    M=N
    for i in range(keta,-1,-1):
        ans += M//(b**i)
        M = M%(b**i)

    if ans==S:
        print(b)
        exit()

print('-1')

Submission status: Time Limit Exceeded

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

    b_cand = []
    for p in range(1, n + 1):
        if p**2 > n:
            break
        b = (n - s) // p + 1
        b_cand.append(b)
    b_cand = b_cand[::-1]

    for b in b_cand:
        if func(b, n) == s:
            return b

    return -1


ans = solve()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import log

n = int(input())
s = int(input())
lb, ub = 1, n + 2
while ub - lb > 1:
    b = (lb + ub) // 2
    if s <= (b - 1) * (int(log(n) / log(b)) + 1):
        ub = b
    else:
        lb = b
for b in range(ub, n + 2):
    m = n
    a = 0
    while m:
        a += m % b
        m //= b
    if a == s:
        print(b)
        exit()
print(-1)

Submission status: Time Limit Exceeded

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, 0, -1):
    nt = n
    st = 0

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

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

print(-1)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=int(input())
if s>n:
  print(-1)
elif s==n:
  print(n+1)
else:
  # 2<=b<=n**0.5 で全探索
  for b in range(2,int(n**0.5)+1):
    tmp=0
    n0=n
    while n0>0:
      tmp+=n0%b
      n0//=b
    if tmp==s:
      print(b)
      exit()
  # n**0.5<bについて
  for p in range(int(n**0.5)+1,0,-1):
    b=(n-s)//p+1
    tmp=0
    n0=n
    while n0>0:
      tmp+=n0%b
      n0//=b
    if tmp==s:
      print(b)
      exit()
  print(-1)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/abc044/tasks/arc060_b

f(b,n)ってbが大きくなるほど大きくなる？(単調増加になる?)
→そんなことはない
nより大きかったら不可能。最小はn進法で桁和1

3桁以上になる物は全探索する
2桁は、良い感じにすべて調べ上げる
実装だるそ～

2桁の時 xyとなるとする
n//b = x
n%b  = y

n = bx+y
x+y = s

(n-S)//x+1 = b
かつ S >= x >= S-b

xについてn-sの約数を全列挙して、bを求める & 下の条件を満たしているか確認すればよい？
"""

def f(b,n):

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

import sys
n = int(input())
s = int(input())

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

for b in range(2,int(n**0.5+10)):

    if f(b,n) == s:
        print (b)
        sys.exit()

#ここからだるいパート
ans = float("inf")

for x1 in range(1,s+1):

    if (n-s) % x1 == 0:

        x2 = (n-s)//x1

        b1 = (n-s)//x1+1
        if b1 ** 2 > n and s >= x1 >= s-b1:
            ans = min(ans , b1)

        b2 = (n-s)//x2+1
        if b2 **2 > n and s >= x2 >= s-b2:
            ans = min(ans , b2)

if ans == float("inf"):
    print (-1)
else:
    print (ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

b = 2
n = int(input())
s = int(input())


while True:
    
    if f(b,n) == s:
        print(b)
        sys.exit()
    if b == 100000000000:
        print(-1)
        sys.exit()
    b = b + 1

Submission status: Time Limit Exceeded

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

No=0
for b in range(2,n+1):
    m=0
    N=n
    while N!=0:
        m+=N%b
        N=N//b
        if m>s:
            break
    if m==s:
        print(b)
        No=1
        break
if n==s:
    print(n+1)
    No =1
if No==0:
    print(-1)

Submission status: Time Limit Exceeded

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

No=0
for b in range(2,n+1):
    m=0
    N=n
    while N!=0:
        m+=N%b
        N=N//b
    if m==s:
        print(b)
        No=1
        break
if n==s:
    print(n+1)
    No =1
if No==0:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.stdin.readline
INF = float("inf")

def digitsum(b, n):
    ans = 0
    while n:
        n, m = divmod(n, b)
        ans += m
    return ans

def solve():
    n = int(input())
    s = int(input())
    if s == n: return n+1
    if s > n: return -1
    for b in range(2, int(n**.5)+1):
        if digitsum(b, n) == s: return b
    ans = INF
    for d in range(1, int(n**.5)+1):
        b = (n - s) // d + 1
        if digitsum(b, n) == s:
            ans = min(ans, b)
    if ans == INF:
        ans = -1
    return ans

if __name__ == "__main__":
    print(solve())

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.stdin.readline

def digitsum(b, n):
    ans = 0
    while n:
        n, m = divmod(n, b)
        ans += m
    return ans

def main():
    n = int(input())
    s = int(input())
    if s == n:
        print(n+1)
        return
    if s > n:
        print(-1)
        return
    for b in range(2, int(n**.5)+1):
        if digitsum(b, n) == s:
            print(b)
            return
    ans = float("inf")
    for d in range(1, int(n**.5)+1):
        b = (n - s) // d + 1
        if digitsum(b, n) == s:
            ans = min(ans, b)
    if ans == float("inf"):
        ans = -1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def primeFactor(N):
    i, n, ret, d, sq = 2, N, {}, 2, 99
    while i <= sq:
        k = 0
        while n % i == 0: n, k, ret[i] = n//i, k+1, k+1
        if k > 0 or i == 97: sq = int(n**(1/2)+0.5)
        if i < 4: i = i * 2 - 1
        else: i, d = i+d, d^6
    if n > 1: ret[n] = 1
    return ret

def divisors(N):
    pf = primeFactor(N)
    ret = [1]
    for p in pf:
        ret_prev = ret
        ret = []
        for i in range(pf[p]+1):
            for r in ret_prev:
                ret.append(r * (p ** i))
    return sorted(ret)

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

N = int(input())
S = int(input())

for b in divisors(abs(N-S)):
    b += 1
    if f(b, N) == S:
        print(b)
        break
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import math


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


def main(n, s):
    if s > n:
        return -1
    elif n == s:
        return n + 1
    else:
        b = 2
        while b * b <= n:
            if digit_sum(b, n) == s:
                return b

        p = 1
        b_min = -1
        while p * p <= n:
            if (n - s) % p == 0:
                b = (n - s) // p + 1
                if digit_sum(b, n) == s:
                    b_min = min(b_min, b) if b_min != -1 else b
            p += 1
        return b_min


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

Submission status: Time Limit Exceeded

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

result = -1
if n == s:
  result = n + 1
elif s > n:
  pass
else:
  sqrt_n = math.floor(math.sqrt(n))
  for b in range(2, sqrt_n + 1):
    temp_n = n
    temp_b = 0
    while temp_n >= b:
      temp_b += temp_n % b
      temp_n = temp_n // b
    if temp_b + temp_n == s:
      result = b
      break
  if result == -1:
    for quot in range(sqrt_n, 0, -1):
      if n - s % quot != 0:
        b = (n - s) // quot + 1
        temp_n = n
        temp_b = 0
        while temp_n >= b:
          temp_b += temp_n % b
          temp_n = temp_n // b
        if temp_b + temp_n == s:
          result = b
          break
print(result)

Submission status: Time Limit Exceeded

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

def Base_10_to_n(X, nn):
    X_dumy = X
    out = ''
    total = 0
    while X_dumy > 0:
        out = str(X_dumy % nn)+out
        total = X_dumy % nn + total
        X_dumy = int(X_dumy / nn)
    return total

#print(Base_10_to_n(119,11))
for b in range(N):
#  N_converted = list(Base_10_to_n(N, b+1))
#  N_converted_int = [int(s) for s in N_converted]
#  if sum(N_converted_int) == S:
#    print('Yes')
  if Base_10_to_n(N, b+2) == S:
    print(b+2)
    exit()

print(-1)

Submission status: Time Limit Exceeded

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 <= 0:
            continue
        if s == f(b, n):
            print(b)
            return
    print(-1)
    return


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

Submission status: Time Limit Exceeded

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)
for i in range(1,ceil(sqrt(n))):
    b=(n-s)//i+1
    if func(b,n)==s:
        ans=min(ans,b)
if ans==10**30:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

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


def bisect_left_callable(fn, x, lo, hi):
    """
    lo から hi-1 のうち、fn の結果が x 以上となる、最も左の値
    bisect.bisect_left と同じ
    https://docs.python.org/ja/3/library/bisect.html
    :param callable fn:
    :param x:
    :param int lo: 最小値
    :param int hi: 最大値 + 1
    :return: lo <= ret <= hi
    """
    while lo < hi:
        mid = (lo + hi) // 2
        if fn(mid) < x:
            lo = mid + 1
        else:
            hi = mid
    return lo


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

for i in range(1, int(math.sqrt(N)) + 1):
    hi = N // i + 1
    lo = N // (i + 1) + 1
    b = bisect_left_callable(lambda x: -f(x, N), -S, lo, hi)
    if f(b, N) == S:
        ans = b
print(ans)

Submission status: Time Limit Exceeded

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


def bisect_left_callable(fn, x, lo, hi):
    """
    lo から hi-1 のうち、fn の結果が x 以上となる、最も左の値
    bisect.bisect_left と同じ
    https://docs.python.org/ja/3/library/bisect.html
    :param callable fn:
    :param x:
    :param int lo: 最小値
    :param int hi: 最大値 + 1
    :return: lo <= ret <= hi
    """
    while lo < hi:
        mid = (lo + hi) // 2
        if fn(mid) < x:
            lo = mid + 1
        else:
            hi = mid
    return lo


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

for i in range(1, int(math.sqrt(N)) + 1):
    hi = N // i + 1
    lo = N // (i + 1) + 1
    b = bisect_left_callable(lambda x: -f(x, N), -S, lo, hi)
    if f(b, N) == S:
        ans = b
print(ans)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

import sys, re
from collections import deque, defaultdict, Counter
from math import 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 n < s:
    print(-1)
elif n == s:
    print(n+1)
else:
    for i in range(2, n+1):
        if f(i, n) == s:
            print(i)
            exit()
    print(-1)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:

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

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

if n < s or (n // 2)+1 < s < n :
    print("-1")
elif s == n:
    print(n+1)
elif s == n//2 +1:
    if n % 2 == 1:
        print(n//2 + 1)
    else:
        print("-1")
elif (n//3) + 2 < s <= n//2:
    print(n-s+1)
elif s == 1:
    def check(n,b):
        if n == 1:
            return b
        else:
            if n % b !=0 :
                return 0
            else:
                return check(n // b,b)
    for b in range(2,rtn):
        r = check(n,b)
        if r:
            print(r)
            exit()
    print(n)
else:
    x = n // s
    if s - (n //(x+1))  <= x:
        x = x + 1
    if 5 < n/(x -1) - n/x :
        for b in range(n//x, n//(x-1)):
            if f(b,n) == s:
                print(b)
                exit()
        for i in range(x-1,2,-1):
            for b in range(n//i + (n//x)//(n//i), n//i + (n//x)//(n//i)  + (2*n//x - n//(x+1))//(x-i)):
                if f(b,n) == s:
                    print(b)
                    exit()
    else:
        for b in range(2,(n//3)+3):
            if f(b,n) == s:
                print(b)
                exit()
    print(n-s+1)

Submission status: Time Limit Exceeded

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

def f(b,n) :
    r = 0
    i = 1
    while n:
        j = n % b
        r += j
        n = (n-j)//b
    return r


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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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)), 0, -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: f = n + 1
if f is None: print(-1)
else: print(f)

Submission status: Time Limit Exceeded

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 = math.pow(n, 0.5)
    i = 2
    while i <= rn:
        if s == calc(i, n):
            print i
            break
        i += 1
    else:
        q = s / i
        p = s % i
        while q < rn:
            b = (n - s) / p + 1
            if s == calc(b, n):
                print b
                break
        else:
            print -1

Submission status: Time Limit Exceeded

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())
rn = math.pow(n, 0.5)
i = 2
while i <= rn:
    if s == calc(i, n):
        print i
        break
    i += 1
else:
    q = s / i
    p = s % i
    while q < rn:
        b = (n - s) / p + 1
        if s == calc(b, n):
            print b
            break
    else:
        print -1

Submission status: Time Limit Exceeded

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,3200000):
    if f(i, n) == s:
        print(i)
        exit(0)


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

print(-1)

Submission status: Time Limit Exceeded

Solution code:
def f(b,n):
	i = n
	a = 0
	while i != 0:
		a += (i%b)
		i = int(i/b)
	return(a)

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

for i in range(2,n + 2):
	if f(i,n) == s:
		print(i)
		break
else:
	print(-1)

Submission status: Time Limit Exceeded

Solution code:
import math,sys
from operator import *

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

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


i = 1
while(True):
    try:
        ret = f(i,n)
    except:
        ret = -1

    if ret == s:
        print(i)
        break
    i+=1

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
n = int(raw_input())
s = int(raw_input())

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

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

for b in xrange(2, n+1):
    if f(b, n) == s:
        print b
        sys.exit()
print -1

Submission status: Accepted

Solution code:
from math import sqrt


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


def divisors(P):
    res = set([])
    for i in range(1, P+1):
        if i**2 > P:
            break
        else:
            if P % i == 0:
                res.add(i)
                res.add(P//i)
    return res


def main():
    N = int(input())
    S = int(input())
    res = 10**18
    if N <= 10**6:
        for b in range(2, N+2):
            if f(b, N) == S:
                res = b
                break
        if res < 10**18:
            print(res)
        else:
            print(-1)
            return

    else:
        #N > 10**6
        for b in range(2, 10**6+2):
            if f(b, N) == S:
                res = b
                break
        if res < 10 ** 18:
            print(res)
            return
        else:
            if N < S:
                print(-1)
                return
            elif N == S:
                print(N+1)
                return
            else:
                div = divisors(N-S)
                for y in div:
                    sub_res = y + 1
                    if f(sub_res, N) == S:
                        res = min(res, sub_res)
                        
                if res < 10**18:
                    print(res)
                else:
                    print(-1)
                return

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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