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:
import math

n = int(input())
s = int(input())
ans = -1
if n > s:
    sqrt_n = math.ceil(math.sqrt(n))
    for b in range(2, sqrt_n + 1):
        m = n
        f = 0
        while m >= b:
            f += (m % b)
            m //= b
        f += m
        if f == s:
            ans = b
            break
    b = sqrt_n
    if ans == -1:
        for p in range(sqrt_n - 1, 0, -1):
            if (n - s) % p == 0:
                b = (n - s) // p + 1
            if n % b + n // b == s:
                ans = b
                break
elif n == s:
    ans = n + 1
print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

def main():
    """
    nのオーダーを見てb < √nまで半分全探索しようという気持ちになるのか・・・？
    そうだとしても√n < bの場合の考察もやや技巧的に思われるが、
    とりあえず√nで切る方策はある種の定石として覚えておくことにする。
    あとは解説pdf参照。
    """
    n = int(input())
    s = int(input())
    if n < s:
        print(-1)
        return
    if n == s:
        print(n + 1)
        return
    for b in range(2, int(n ** 0.5) + 1):
        val = 0
        num = n
        while num >= b:
            val += num % b
            num //= b
        val += num
        if val == s:
            print(b)
            return
    for p in range(int(n ** 0.5), 0, -1):
        if (n - s) % p != 0: continue
        b = (n - s) // p + 1
        val = 0
        num = n
        while num >= b:
            val += num % b
            num //= b
        val += num
        if val == s:
            print(b)
            return
    print(-1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
def yakusu(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())
def NIJIGEN(H): return [list(input()) for i in range(H)]
N=int(input())
K=int(input())
if N==K:
  print(N+1)
  exit()
if N<K:
  print(-1)
  exit()
L=list()
setL=set()
#N-Kはa-1の倍数
L=yakusu(N-K)
L=[i+1 for i in L]
for i in L:
  ans=0
  m=N
  while True:
    if m<i:
      ans+=m
      break
    else:
      ans+=m%i
      m=m//i
  if ans==K:
    print(i)
    exit()
print(-1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def function(b, n):
    if n < b:
        return n
    else:
        return function(b, n//b) + n % b
from math import sqrt
def divs(n):
  d=[]
  for x in range(1,int(sqrt(n))+1):
    if n%x==0:
      d.extend([x,n//x])
  d=list(set(d))
  d.sort()
  return d

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

    if n < s:
        return("-1")
    elif n == s:
        return(n+1)
    else:
        ds = divs(n - s)
        for x in ds:
            if s == function(x+1,n):
                return(x+1)
        else:
            return("-1")

print(main())

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
N = int(input())
S = int(input())

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

MAX = 10 ** 6
for b in range(2, MAX + 1):
    res = f(b, N)
    if res == S:
        print(b)
        exit()
x = N - S
if x < 0:
    print(-1)
elif x == 0:
    print(N + 1)
else:
    ans = -1
    for p in range(1, MAX + 1):
        if x % p == 0:
            b = (x // p) + 1
            if b > MAX and N // b == p:
                ans = b
    print(ans)

Submission status: Accepted

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

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

for i in range(2, math.floor(math.sqrt(n)) + 1):
    new_n = n
    remain = 0
    while new_n > 0:
        remain += new_n % i
        new_n //= i

    if remain == s:
        print(i)
        exit()

for i in range(math.floor(math.sqrt(n)) + 1, 0, -1):
    b = (n - s) // i + 1
    st = n % b + n // b
    if n // b != b and st == s:
        print(b)
        exit()

print(-1)

Submission status: Accepted

Solution code:
def f(b,n):
  if 0<n:
    return n%b+f(b,n//b)
  else:
    return 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()

if n==s:
  print(n+1)
else:
  print(-1)

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())

N,s = I(),I()


def digit_sum(b,n):  # nのb進法での桁和
    res = 0
    while n > 0:
        res += n % b
        n //= b
    return res


M = int(N**.5)+1
for b in range(2,M+1):
    if digit_sum(b,N) == s:
        print(b)
        break
else:  # N = b*q + r と除算して考える(b > M より 0 <= q,r < b)
    ans = 10**12
    for q in range(1,M):
        r = s-q
        if (N-r) % q == 0:
            b = (N-r)//q
            if M < b <= N and 0 <= r < b:
                ans = min(ans,b)
    if N == s:  # q = 0 の場合
        ans = min(ans,N+1)
    print(ans if ans != 10**12 else -1)

Submission status: Accepted

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
        if b > 1:
            b_cand.append(b)
    b_cand = b_cand[::-1]

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

    return -1


ans = solve()
print(ans)

Submission status: Accepted

Solution code:
def divisor(n):
    divisors = []
    i = 1
    while i * i < n:
        if n % i == 0:
            divisors.append(i)
            divisors.append(n // i)
        i += 1
    if i * i == n:
        divisors.append(i)
    divisors.sort()
    return divisors

n = int(input())
s = int(input())
if n == s:
    print(n + 1)
    exit()
if n < s:
    print(-1)
    exit()
sr = int(n ** 0.5)
for b in range(2, sr + 1):
    m = n
    a = 0
    while m:
        a += m % b
        m //= b
    if a == s:
        print(b)
        exit()
for d in divisor(n - s):
    b = d + 1
    if b <= sr:
        continue
    q = (n - s) // d
    r = n % b
    if q + r == s:
        print(b)
        exit()
print(-1)

Submission status: Accepted

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

sq = int(math.sqrt(n))


# 2 <= d <= √n
for i in range(2, sq+1):
    nt = n
    st = 0

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

    if st == s:
        print(i)
        exit()
    
# √n < d <= n
for i in range(sq+1, 0, -1):
    b = (n - s) // i + 1
    
    st = n % b + n // b

    if n // b != b and st == s:
        print(b)
        exit()

print(-1)

Submission status: Accepted

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:
        if ok(i, N, S):
            return i

        i += 1

    return 1 << 60


def solve2():
    i = 1
    ret = 1 << 60
    while i * i <= N:
        b = (N - S) // i + 1
        if ok(b, N, S):
            ret = min(ret, b)
        i += 1

    return ret


def ok(b, N, S):
    if b <= 1:
        return False

    s, n = 0, N
    while n > 0:
        s += n % b
        n //= b

    return s == S



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


print(solve())

Submission status: Accepted

Solution code:
import copy
n=input()
s=input()
ln=len(n)
ls=len(s)
n=int(n)
s=int(s)
if n==s:
    print(n+1)
elif n<s:
    print(-1)
else:
    for b in range(2,pow(10,6)+1):
        N = copy.deepcopy(n)
        f = 0
        while N >= b:
            f += N % b
            N = N // b
        f += N
        if f == s:
            print(b)
            exit()
    ans=-1
    for p in range(1,pow(10,6)+1):
        if (n-s)%p==0:
            b=(n-s)//p+1
        N = copy.deepcopy(n)
        f = 0
        while N >= b:
            f += N % b
            N = N // b
        f += N
        if f == s:
            ans=b
    print(ans)

Submission status: Accepted

Solution code:
from math import sqrt

def divs(n):
  d=[]
  for x in range(1,int(sqrt(n))+1):
    if n%x==0:
      d.extend([x,n//x])
  d=list(set(d))
  d.sort()
  return d

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

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

if n<s:
  print(-1)
  exit()
elif n==s:
  print(n+1)
  exit()
else:
  ds=divs(n-s)
  for x in ds:
    if s==f(x+1,n):
      print(x+1)
      exit()
print(-1)

Submission status: Accepted

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

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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

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

    for i in range(2, n):
        k = i ** 2
        if k > n:
            break
        x = n
        cur = 0
        while x > 0:
            cur += x % i
            x = x // i

        if cur == s:
            print(i)
            sys.exit()

    ans = INF
    for i in range(1, n):
        k = i ** 2
        if k >= n:
            break
        if (n - s) % i == 0:
            b = (n-s) // i + 1
            p = n // b
            q = n % b
            if p + q == s:
                ans = min(ans,b)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


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


def solve():
    """
    87654
    138
    -----
    100

    87654
    45678
    -----
    -1

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

    4
    if b>math.sqrt(n) then n=pb+q, p, q < b
                           s=p+q
    n-s=p*(b-1), b-1 >= p
    """
    if n-s < 0:
        return -1
    if n == s:
        return n+1
    for p in range(math.ceil(math.sqrt(n-s)), 0, -1):
        if (n-s)%p == 0 and f((n-s)//p+1, n) == s:
            return (n-s)//p+1
    return -1


if __name__ == '__main__':
    #print(f(10, 87654))
    #print(f(100, 87654))
    print(solve())

Submission status: Accepted

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
    if not b.is_integer():continue
    b=int(b)
    tmp=0
    n0=n
    while n0>0:
      tmp+=n0%b
      n0//=b
    if tmp==s:
      print(b)
      exit()
  print(-1)

Submission status: Accepted

Solution code:
n = int(input())
s = int(input())
if s == n:
    print(n+1)
    exit()
if s > n%2+n//2:
    print(-1)
    exit()
    

ans = float("INF")
for i in range(2,int(n**0.5)+1):
    x = n
    count = 0
    while x >= i:
        count += x%i
        x //= i
    if count + x == s:
        print(i)
        exit()
now = 2
li = int(n**0.5)+1
while True:

    x = n//now
    if x < li:
        break
    count = 0
    y = n
    while y >= x:
        count += y%x
        y //= x
    count += y
    if count <= s and (s-count)%now == 0:
        z = x-n//(now+1)
        if (s-count)//now < z:
            ans = x-(s-count)//now
    now += 1



print(min(ans,n-s+1))

Submission status: Accepted

Solution code:
n = int(input())
s = int(input())
if s == 1 and n == 1:
    print(2)
    exit()
if s > n:
    print(-1)
    exit()
if n%2 == 0 and n > s > n//2:
    print(-1)
    exit()
if n%2 == 1 and n > s > n//2+1:
    print(-1)
    exit()

ans = float("INF")
for i in range(2,int(n**0.5)+1):
    x = n
    count = 0
    while x >= i:
        count += x%i
        x //= i
    if count + x == s:
        print(i)
        exit()
now = 2
li = int(n**0.5)+1
while True:

    x = n//now
    if x < li:
        break
    count = 0
    y = n
    while y >= x:
        count += y%x
        y //= x
    count += y
    if count <= s and (s-count)%now == 0:
        z = x-n//(now+1)
        if (s-count)//now < z:
            ans = x-(s-count)//now
    now += 1

if s == n:
    print(min(ans,n+1))
else:
    print(min(ans,n-s+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
if n == s:
  print(n+1)
  exit()
U = int(n**0.5)+100
for b in range(2, U+1):
  if f(b, n) == s:
    print(b)
    exit()
for p in range(U-1, 0, -1):
  if (n-s)%p:
    continue
  b = (n-s)//p + 1
  if b < 2:
    continue
  if f(b, n) == s:
    print(b)
    exit()
print(-1)

Submission status: Accepted

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):
#for b in range(2,n+2):
  ss=f(b,n)
  if ss==s:
    print(b)
    sys.exit(0)

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

Submission status: Accepted

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

Solution code:
N=int(input())
S=int(input())
res = 0
for i in range(2,int(N**0.5)+1):
    tmp = N
    tmp2 = 0
    while tmp > 0:
        tmp2 += tmp%i
        tmp = tmp // i
    if tmp2==S:
        res = i
        break
if res == 0:
    for i in range(int(N**0.5)+1,0,-1):
        b = (N-S)//i + 1
        if i*(b-1)+S != N:
            continue
        tmp = N
        tmp2 = 0
        if b<=1:
            continue
        while tmp > 0:
            tmp2 += tmp % b
            tmp = tmp // b
        if tmp2 == S:
            res = b
            break
if N==S:
    print(N+1)
elif res==0 or N<S:
    print(-1)
else:
    print(res)

Submission status: Accepted

Solution code:
def solve(n, s):
    if n < s:
        return -1
    if n == s:
        return n + 1

    sqn = int((n - 1) ** 0.5) + 1
    # 3桁以上
    for b in range(2, sqn + 1):
        tmp = 0
        k = n
        while k > 0:
            d, m = divmod(k, b)
            tmp += m
            k = d
        if tmp == s:
            return b
    # 2桁
    for p in range(sqn - 1, 0, -1):
        b, m = divmod(n - s, p)
        if m != 0:
            continue
        b += 1
        if p + n % b == s:
            return b
    return -1


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

Submission status: Accepted

Solution code:
from math import sqrt


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


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

for b in range(2, int(sqrt(N)) + 1):
    if f(b, N, S):
        print(b)
        exit()

for p in range(int(sqrt(N)), 0, -1):
    if (N - S) % p == 0:
        b = (N - S) // p + 1
        q = N - p * b
        if b > p >= 0 and b > q >= 0 and p + q == S:
            print(b)
            exit()

print(-1)

Submission status: Accepted

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を求める & 下の条件を満たしているか確認すればよい？
上の条件を満たしている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,10**6):

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

        x2 = (n-s)//x1

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

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

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

Submission status: Accepted

Solution code:
# solution

def f(mike, nim):
  return nim % mike + f(mike, nim // mike) if nim > 0 else 0

nim = int(input())
s = int(input())

for i in range(2, 5**8):
  if f(i, nim) == s:
    print(i)
    exit()

for i in range(nim - s >> 18, 0, -1):
  if f((nim - s) // i + 1, nim) == s:
    print((nim - s) // i + 1)
    exit()

print(nim + 1 if nim == s else -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)

def solve(N, S):
    if S > N:
        return -1
    elif N == S:
        return N+1
    else:
        for b in range(2, int(N**(1/2))+1):
            if f(b, N) == S:
                return b
        for p in range(int(N**(1/2)), 0, -1):
            if (N - S) % p == 0:
                b = (N - S) // p + 1
                if f(b, N) == S:
                    return b
        return -1

print(solve(N, S))

Submission status: Accepted

Solution code:
import math

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

b = -1

def keisan(k, w):
  l = []
  while k >= w:
    l.append(k % w)
    k = k // w
  else:
    l.append(k)
  return (sum(l))

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

n_r = math.floor(math.sqrt(n))

for i in range(2, n_r+1):
  if keisan(n, i) == s:
    b = i
    print(b)
    exit()

b_list = []    
    
for i in range(1, n_r+1):
  w = n - s
  syou = w // i
  amari = w % i
  if amari == 0:
    b_kouho = syou + 1
    b_list.append(b_kouho)
#    print(b_list)

b_kansei = []

for b in b_list:
  b_ = keisan(n, b)
  if b_ == s:
    b_kansei.append(b)
#    print("b_kanseiは" + str(b_kansei))

if b_kansei != []:
  print(min(b_kansei))
else:
  print(-1)

Submission status: Accepted

Solution code:
import math

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

def _func(b,n):
  x = n
  ret = 0
  while True:
    if b > x:
      return ret + x
    else:
      ret += x % b
      x = math.floor(x/b)

def solve(n,s):
  if n == s:
    return n+1
  ans = float('inf')
  for b in range(2,math.floor(math.sqrt(n))+1):
    if _func(b,n) == s:
      return b

  for p in range(1,math.floor(math.sqrt(n))+1):
    if (n-s) % p == 0:
      b = int((n-s)/p)+1
      if b < 2:
        continue
      if _func(b, n) == s:
        ans = min(ans, b)

  if ans < float('inf'):
    return ans
  else:
    return -1

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

Submission status: Accepted

Solution code:
n=int(input())
s=int(input())
if s==n:
  print(n+1)
  exit()
def f(x):
  m=n
  t=0
  while m:
    t+=m%x
    m//=x
  return t
for b in range(2,int(n**0.5)+2):
  if f(b)==s:
    print(b)
    exit()
for p in range(1,int(n**0.5))[::-1]:
  q=s-p
  b=(n-s)//p+1
  if 1<=p<b and 0<=q<b and (n-s)%p==0:
    b=(n-s)//p+1
    if f(b)==s:
      print(b)
      exit()
print(-1)

Submission status: Accepted

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

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

m = int((n-1)**.5) + 2
for i in range(2, m):
  t = 0
  f = n
  while f:
    t += f % i
    f //= i
  if t == s:
    print(i)
    exit(0)

a = 10**12
for i in range(1, min(m, s+1)):
  j = s - i
  if (n - j) % i == 0:
    b = (n - j) // i
    if j < b and i < b:
      a = min(a, b)
print(a if a < 10**12 else -1)

Submission status: Accepted

Solution code:
# python 3.4.3
import sys
input = sys.stdin.readline

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


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N = int(input())
S = int(input())

ans = -1
if S==N:
    ans = N+1
else:
    # bをN^(1/2)まで全探索
    for b in range(2, int(N**.5)+1):
        if f(b,N)==S:
            ans = b
            break

# まだ答えが見つからなければ
if ans == -1:
    # bがN^(1/2)より大きい可能性が残っており、b進数で表すと2桁
    # 1 <= p < b, N = pb+q <= pb < p^2, p > N^(1/2) なので pで全探索
    # p+q = S より b = (N-S)/p+1
    for p in range(int(N**.5)+1,0,-1):
        b = (N-S)//p + 1
        # bが1のときは対象外にしないと無限ループ！
        if b >= 2 and f(b,N)==S:
            ans = b
            break

print(ans)

Submission status: Accepted

Solution code:
import math

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

"""
kari1 = 87654
kari2 = 30          #10
kari1 = 87654
kari2 = 138         #100
kari1 = 87654
kari2 = 45678       #-1
kari1 = 31415926535
kari2 = 1           #31415926535
kari1 = 1
kari2 = 31415926535 #-1
n = int(kari1)
s = int(kari2)
"""
n = int(input())
s = int(input())

if n < s:
    print(-1)
elif n == s:
    print(n + 1)
else:
    b = 2
    while b * b <= n:
        if s == f(b, n):
            is_b = True
            break
        b += 1
    if b * b <= n:
        print(b)
    else:
        p = 1
        ans = -1
        while p * p <= n:
              if (n - s) % p != 0:
                    p += 1
                    continue
              else:
                    b = (n - s) // p + 1
                    if s == f(b, n):
                        ans = min(b, ans) if ans != -1 else b
              p += 1
        print(ans)

Submission status: Accepted

Solution code:
def D(n,d):
  r=0
  while n>0:
    r=r+n%d
    n=n//d
  return r

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

n=int(input())
s=int(input())
if n-s==0:
  print(n+1)
  exit()
if s>n:
  print(-1)
  exit()

A=make_divisors(n-s)
for i in range(len(A)):
  if D(n,A[i]+1)==s:
    print(A[i]+1)
    exit()
print(-1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    n=I()
    s=I()
    
    if s==n:
        print(n+1)
    elif s>n:
        print(-1)
    else:
        #nをb進法にして，桁和を計算
        def calc(b,n):
            temp=0
            while n!=0:
                temp+=n%b
                n=n//b
            return temp
        
        ans=1000000000000
        N=1000000
        
        #まずはbを10**6程度まで探索
        for b in range(2,N):
            if calc(b,n)==s:
                ans=b
                break
            
        if ans!=1000000000000:
            print(ans)
            
        #もし，b>10**6で，うまく表現できるならばそれは2桁となる，b>10**6より，上位桁は最高でも10**6程度(max_n=10**11だから)
        else:
            #a1が上位の桁,a0が下位の桁
            for a1 in range(1,N):
                a0=s-a1
                if a0<0:
                    break
                if (n-a0)%a1==0:
                    b=(n-a0)//a1
                    if b>1000000 and a0<b and a1<b:
                        ans=min(ans,b)
                        
            if ans!=1000000000000:
                print(ans)
            else:
                print(-1)
        
        
    
    
    
    
    
    
            
    
        

main()

Submission status: Accepted

Solution code:
from math import floor, sqrt, ceil


def f(b, n):
    if n < b:
        return n

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


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

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

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

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

print(-1)

Submission status: Accepted

Solution code:
from math import floor, sqrt, ceil


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

    if n < b:
        return n

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


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

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

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

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

print(-1)

Submission status: Accepted

Solution code:
from math import floor, sqrt, ceil


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

    if n < b:
        return n

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


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

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

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

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

print(-1)

Submission status: Accepted

Solution code:
import math
import sys

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

up = math.sqrt(n)

def colsum(num, base):
    if num < base:
        return num
    else:
        return num%base + colsum(num//base,base)

#s >= n
if s == n:
    print(n+1)
elif s > n:
    print(-1)
else:
    #sqrt(n)まで探索
    for i in range(2,int(up)+1):
        if colsum(n,i) == s:
            print(i)
            sys.exit()

    #2桁しかあり得ない場合(sqrt(n)<b<n)
    for j in range(int(up),0,-1):
        if (n-s)%j == 0:
            b = (n-s)/j + 1
            if colsum(n,b) == s and b > 1:
                print(int(b))
                sys.exit()

    print(-1)

Submission status: Accepted

Solution code:
n = int(input())
s = int(input())
x = int(n**0.5)+1
def dsum(x,t):
  ret = 0
  while x>0:
    ret += x%t
    x //= t
  return ret
for i in range(2,x+1):
  if dsum(n,i) == s:
    print(i)
    exit()
for i in range(x,0,-1):
  if (n-(s-i))%i == 0:
    digit = (n-(s-i))//i
    if 0 < i < digit and 0 <= s-i < digit:
      print((n-(s-i))//i)
      exit()
if n == s:
  print(n+1)
  exit()
print(-1)