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:
#!/usr/bin/env python3
import sys


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


def sqrt(n: int):
    lb = 0
    hb = n + 1
    while hb - lb > 1:
        m = (lb + hb) // 2
        if m * m <= n:
            lb = m
        else:
            hb = m
    return lb


def solve(n: int, s: int):
    if s == n:
        print(n + 1)
        return
    sn = sqrt(n)
    for b in range(2, sn + 1):
        if f(b, n) == s:
            print(b)
            return
    for p in reversed(range(1, sn + 1)):
        q = s - p
        if q < 0:
            continue
        b, r = divmod(n - q, p)
        if r != 0 or b <= p:
            continue
        if f(b, n) == s:
            print(b)
            return
    print(-1)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    s = int(next(tokens))  # type: int
    solve(n, s)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

No=0
if n==s:
    print(n+1)
    No =1
else:
    for b in range(2,int(n**0.5)+2):
        m=0
        N=n
        while N!=0:
            m+=N%b
            N=N//b
            if m>s:
                break    
        if m==s:
            print(b)
            No=1
            exit()
    for p in range(int(n**0.5-1),0,-1):
        b = float(n-s)/float(p)+1.0
        if abs(b-int(b))<10**(-10)and b>0:
            b=int(b)
            m=0
            N=n
            while N!=0:
                m+=N%b
                N=N//b
                if m>s:
                    break    
            if m==s:
                print(b)
                No=1
                exit()
if No==0:
    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:
def f(b, n):
    return n if n < b else n % b + f(b, n // b)

def solve():
    N, S = map(int, open(0))

    if N == S:
        return N + 1

    sqr = int(N ** 0.5)

    for b in range(2, sqr + 1):
        if f(b, N) == S:
            return b

    M = N - S
    for p in reversed(range(1, sqr + 1)):
        b = M // p + 1
        if b >= 2 and f(b, N) == S:
            return b

    return -1


print(solve())

Submission status: Accepted

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 b < 2: continue
        if digitsum(b, n) == s:
            ans = min(ans, b)
    if ans == INF:
        ans = -1
    return ans

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

Submission status: Accepted

Solution code:
n = int(input())
s = int(input())
A = []
if n >= s:
  for i in range(1, int((n-s)**(1/2))+1):
    if (n - s) % i == 0:
      if (n - s) // i != i:
        A.append(i+1)
        A.append((n - s) // i + 1)
      else:
        A.append(i+1)
def digit_sum(b, m):
  if m < b:
    return m
  else:
    return digit_sum(b, m // b) + m % b
B = []
for i in A:
  if digit_sum(i, n) == s:
    B.append(i)
if n < s:
  print(-1)
else:
  if n == s:
    print(n+1)
  else:
    if B == []:
      print(-1)
    else:
      print(min(B))

Submission status: Accepted

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

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

if n<s:
    print(-1)
elif n==s:
    print(n+1)
else:
    for i in range(2,int(math.sqrt(n))+1):
        if f(i,n)==s:
            print(i)
            break
    else:
        for p in range(int(math.sqrt(n)),0,-1):
            if (n-s)%p==0:
                b=(n-s)//p+1
                #print(b)
                #print(f(b,n))
                if f(b,n)==s:
                    print(b)
                    break
        else:
            print(-1)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N = I()
    S = I()
    
    if N==S:
        print(N+1)
        return 

    def check(N,b):
        res = 0
        while N:
            res += N%b
            N//=b
        return res == S


    for b in range(2,int(sqrt(N)+1)):
        if check(N,b):
            print(b)
            return
    for p in range(1,int(sqrt(N)+1))[::-1]:
        b = (N-S+p)//p
        if b>=2 and check(N,b):
            print(b)
            return
    print(-1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N = I()
    S = I()
    
    if N==S:
        print(N+1)
        return 

    def check(N,b):
        res = 0
        while N:
            res += N%b
            N//=b
        return res == S


    for b in range(2,int(sqrt(N)+1)):
        if check(N,b):
            print(b)
            return
    for p in range(1,int(sqrt(N)+1))[::-1]:
        b = (N-S)//p + 1
        q = S - p
        N_ = N - q

        if N_ % p == 0 and 0 <= q < N_//p and p!=N_//p:
            print(N_//p)
            return
    print(-1)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

import math

ans = float('inf')

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

for b in range(2, 10**6):
    res = n
    tmp = 0
    while res > 0:
        tmp += res % b
        res = (res-res % b)//b
    if tmp == s:
        ans = min(ans, b)

if n < 10**6:
    print(ans if ans != float('inf') else -1)
    exit()

for p in range(1, 10**6):
    if (n-s) % p != 0:
        continue
    else:
        b = (n-s)//p + 1
        if p < b and n % b == s-p:
            ans = min(ans, b)
        
print(ans if ans != float('inf') else -1)

Submission status: Accepted

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

import math

ans = float('inf')

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

for b in range(2, 10**6):
    res = n
    tmp = 0
    while res > 0:
        tmp += res % b
        res = (res-res % b)//b
    if tmp == s:
        ans = min(ans, b)

if n < 10**6:
    print(ans if ans != float('inf') else -1)
    exit()

for p in range(1, 10**6):
    if (n-s) % p != 0:
        continue
    else:
        b = (n-s)//p + 1
        if b > math.sqrt(n) and n % b == s-p:
            ans = min(ans, b)
        
print(ans if ans != float('inf') else -1)

Submission status: Accepted

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

def get_divisor(n):
    res = []
    for i in range(1,int(n**0.5)+1):
        if n%i==0:
            res.append(i)
            res.append(n//i)
    res = list(set(res))
    res.sort()
    return res

n = int(input())
s = int(input())
ans = -1

for b in range(2,int(n**0.5)+1):
    if f(b,n)==s:
        ans = b
        break

if ans==-1 and n>=s:
    div = get_divisor(n-s)
    div.append(n)
    for b in div:
        b += 1
        if f(b,n)==s:
            ans = b
            break

print(ans)

Submission status: Accepted

Solution code:
import math

n = int(input())
s = int(input())
ans = -1

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

if n < s:
    ans = -1
elif n == s:
    ans = n+1
else:
    for b in range(2,int(math.sqrt(n))+1):
      if func(b, n) == s:
          ans = b
          break

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

Submission status: Accepted

Solution code:
import math
n, s = [int(input()) for _ in range(2)]

def f(b,n):
    if n<b:
        return n
    elif n >= b:
        # // 少数切り捨ての割り算
        return f(b,(n//b)) + (n%b)

# nとsが同じであれば、n+1が答えであることは自明
# n==s==2の場合、bが2と仮定すると、
# 2進数で各桁の足し算を行うため、
# 2を2進数表記にすると10となる。
# 1+0 = 1となるため、偽

# n==s==2の場合、bが3と仮定すると、
# 3進数で各桁の足し算を行うため、
# 3を2進数表記にすると2となる。
# 2 = 2となるため、真
if n == s:
    print(n + 1)
    exit()
    
# 解がプラスであるときの計算
# 2～√nまでの計算
for b in range(2, int(math.sqrt(n))+1):
    if f(b,n) == s:
        print(b)
        exit()

# √n～0までの計算。-1づつする
for i in range(int(math.sqrt(n))+1,0,-1):
    b = (n-s)//i +1
    if b >1 and f(b,n) ==s:
            print(b)
            exit()

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
    elif n >= b:
        # // 少数切り捨ての割り算
        return f(b,(n//b)) + (n%b)

# nとsが同じであれば、n+1が答えであることは自明
# n==s==2の場合、bが2と仮定すると、
# 2進数で各桁の足し算を行うため、
# 2を2進数表記にすると10となる。
# 1+0 = 1となるため、偽

# n==s==2の場合、bが3と仮定すると、
# 3進数で各桁の足し算を行うため、
# 3を2進数表記にすると2となる。
# 2 = 2となるため、真
if n == s:
    print(n + 1)
    exit()
    
# 解がプラスであるときの計算
# 2～√nまでの計算
for b in range(2, int(math.sqrt(n))+1):
    if f(b,n) == s:
        print(b)
        exit()

# √n～0までの計算。-1づつする
for i in range(int(n**.5)+1,0,-1):
    b = (n-s)//i +1
    if b >1 and f(b,n) ==s:
            print(b)
            exit()

print(-1)

Submission status: Accepted

Solution code:
import math
import sys

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

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

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

for i in range(2,int(math.sqrt(n))+1):
    if f(i,n)==s:
        print(i)
        break
else:
    lst=make_divisors(n-s)
    for u in lst:
        if f(u+1,n)==s:
            print(u+1)
            break
    else:
        print(-1)

Submission status: Accepted

Solution code:
def primeFactor(N):
    i = 2
    ret = {}
    n = N
    mrFlg = 0
    while i**2 <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
            ret[i] = k
        i += 1
        if i == 101 and n >= (2**20):
            def findFactorRho(N): # Primeでないことを確認したものを引数とする。
                def gcd(a, b):
                    while b: a, b = b, a % b
                    return abs(a)
                def f(x, c):
                    return ((x ** 2) + c) % N
                semi = [N]
                for c in range(1, 99):
                    x, y, d = 2, 2, 1
                    while d == 1:
                        x = f(x, c)
                        y = f(f(y, c), c)
                        d = gcd(abs(x-y), N)
                    if d != N:
                        if isPrimeMR(d): return d
                        elif isPrimeMR(N//d):
                            return N//d
                        else:
                            semi.append(d)
            while True:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                    break
                else:
                    mrFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                        ret[j] = k
                if n == 1: break

    if n > 1: ret[n] = 1
    if mrFlg > 0:
        def dict_sort(X):
            Y={}
            for x in sorted(X.keys()):
                Y[x] = X[x]
            return Y
        ret = dict_sort(ret)
    return ret

def isPrimeMR(n):
    if n == 2:
        return True
    if n == 1 or n & 1 == 0:
        return False
    d = (n - 1) >> 1
    while d & 1 == 0:
        d >>= 1

    for a in [2, 3, 5, 7, 11, 13, 17, 19, 23]:
        t = d
        y = pow(a, t, n)
        while t != n - 1 and y != 1 and y != n - 1:
            y = (y * y) % n
            t <<= 1

        if y != n - 1 and t & 1 == 0:
            return False
        return True

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())
if N < S:
    print(-1)
elif N == S:
    print(N+1)
else:
    for b in divisors(N-S):
        b += 1
        if f(b, N) == S:
            print(b)
            break
    else:
        print(-1)

Submission status: Accepted

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())
if N < S:
    print(-1)
elif N == S:
    print(N+1)
else:
    for b in divisors(N-S):
        b += 1
        if f(b, N) == S:
            print(b)
            break
    else:
        print(-1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()

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

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

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

    # 2 <= b <= sqrt(n) を全探索
    k=int(n**.5)
    for b in range(2,k+1):
        if(f(b,n)==s):
            print(b)
            return

    # sqrt(n) < b <= n を考える
    B=[]
    for p in range(1,k+1):
        if((n-s)%p): continue
        b=(n-s)//p+1
        if(b<2): continue
        if(f(b,n)==s):
            B.append(b)

    print(min(B) if(B) else -1)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()

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

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

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

    # 2 <= b <= sqrt(n) を全探索
    k=0
    while((k+1)**2<=n): k+=1
    for b in range(2,k+1):
        if(f(b,n)==s):
            print(b)
            return

    # sqrt(n) < b <= n を考える
    B=[]
    for p in range(1,k+1):
        if((n-s)%p): continue
        b=(n-s)//p+1
        if(b<2): continue
        if(f(b,n)==s):
            B.append(b)

    print(min(B) if(B) else -1)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()

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

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

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

    # 2 <= b <= sqrt(n) を全探索
    k=int(n**.5)
    for b in range(2,k+2):
        if(f(b,n)==s):
            print(b)
            return

    # sqrt(n) < b <= n を考える
    B=[]
    for p in range(1,k+1):
        if((n-s)%p): continue
        b=(n-s)//p+1
        if(b<2): continue
        if(f(b,n)==s):
            B.append(b)

    print(min(B) if(B) else -1)
resolve()

Submission status: Accepted

Solution code:
def f(p, q):
    if q < p:
        return q
    else:
        return f(p, q//p) + q%p

n = int(input())
s = int(input())
flag = 0
if n < s:
    print(-1)
    flag = 1
if flag == 0 and n == s:
    print(n+1)
    flag = 1
if flag == 0:
    for i in range(2, int(n**0.5)+2):
        if f(i, n) == s:
            print(i)
            flag = 1
            break
if flag == 0:
    for i in range(int(n**0.5), 0, -1):
        if (n-s)%i == 0:
            if f((n-s)//i+1, n) == s:
                print((n-s)//i+1)
                flag = 1
                break

if flag == 0:
    print(-1)

Submission status: Accepted

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
            b += 1

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

Solution code:
def examD():
    def f(b, n):
        if n < b:
            return n
        else:
            return f(b, n // b) + n % b
    n = I(); s = I()
    ans = -1
    if s==n:
        ans = n+1
    else:
        loop = int(n**(0.5))
        for b in range(2,loop+1):
            if f(b,n)==s:
                ans = b
                break
    if ans==-1:
        for p in range(loop+1,0,-1):
            b = (n-s)//p + 1
            if b >= 2 and f(b,n)==s:
                    ans = b
                    break

    print(ans)

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Submission status: Accepted

Solution code:
# python3 (3.4.3)
import sys
input = sys.stdin.readline

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

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

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(base, n):
    # 10進数 n を, base 進数に変換して各桁を足し合わせる
    total = 0
    while n > 0:
        # print('除', n // base, 'あまり', n % base)
        total += n % base
        n = n // base
    return total


def solve():
    N, S = int(input()), int(input())
    # print(N, S)

    if N == S:
        return N + 1

    for b in range(2, int(math.sqrt(N)) + 1):
        if f(b, N) == S:
            return b

    largest = N**2
    lowest = largest
    for p in range(1, int(math.sqrt(N)) + 1):
        b = int((N - S) / p + 1)
        if b > 1 and f(b, N) == S:
            lowest = min(lowest, b)

    if not lowest == largest:
        return lowest

    return -1


if __name__ == '__main__':
    res = solve()
    print(res)

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),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:
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:
def f(b,n):
    ans = 0
    if n<b:
        return n
    else:
        return f(b,n//b)+n%b
def main():
    n=int(input())
    s=int(input())
    if n==s:
        return n+1
    if n <s:
        return -1

    nsq=int(n**0.5+1)
    for b in range(2,nsq+1):
        if f(b,n)==s:
            return b
    m=n-s
    msq=int(m**0.5+1)
    for p in range(msq,0,-1):
        if m%p:
            continue
        b=m//p+1
        if f(b,n)==s:
            return b
    return -1

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

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


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


n = int(input())
s = int(input())
bmax = math.floor(math.sqrt(n))

for b in range(2, bmax + 1):
    if f(b, n) == s:
        print(b)
        exit()
for k in range(bmax - 1, 0, -1):
    bb = n // k
    remaining = s - k - n % bb
    if remaining < 0 or remaining >= bb - remaining // k:
        continue
    if remaining % k == 0:
        print(bb - remaining // k)
        exit()
if n > 1 and s == 1:
    print(n)
    exit()
if s == n:
    print(n + 1)
    exit()
print(-1)

Submission status: Accepted

Solution code:
import math

n = int(input())
s = int(input())
ans = -1

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

#
if n == s: ans = n+1
for i in range(2, int(math.sqrt(n))+1):
    if f(i, n) == s:
        ans = i
        break
if ans == -1:
    for i in range(int(math.sqrt(n)), 0, -1):
        b = int((n-s) / i + 1)
        if b >= 2 and f(b,n) == s:
            ans = b
            break

print(ans)

Submission status: Accepted

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

result = -1
if n == s:
  result = n + 1
elif s > n:
  pass
else:
  temp_sqrt_n = math.floor(math.sqrt(n))
  for b in range(2, temp_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:
    temp_sqrt_n = math.floor(math.sqrt(n - 1))
    for quot in range(temp_sqrt_n, 0, -1):
      if n - s % quot != 0:
        b = (n - s) // quot + 1
        if quot + n % b == s:
          result = b
          break
print(result)

Submission status: Accepted

Solution code:
n=int(input())
s=int(input())
ans="-1"
def f(b,n):
    if n<b:
        return n
    else:
        return f(b,n//b)+n%b
if n==s:
    ans=n+1
for b in range(2,int(n**(1/2)+1)):
    if f(b,n)==s:
        ans=b
        break
if ans=="-1":
    for p in range(int(n**(1/2)+1),0,-1):
        b=int((n-s)/p)+1
        if b>=2:
            if f(b,n)==s:
                ans=b
                break
print(ans)

Submission status: Accepted

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

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

res = -1

import sys
import math

#sys.setrecursionlimit(10000000)

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

bound = int(math.sqrt(n))

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

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

print(res)

Submission status: Accepted

Solution code:
import math
#平方オーダーなら収まるので平方根とって方針を分ける
n = int(input())
s = int(input())
if n == s:
  print(n + 1)
  exit(0)
def sqrt(k):
  return int(math.sqrt(k))
def digitsum(b, m):
  if m < b:
    return m
  return digitsum(b, m // b) + m % b
#√nより小さいなら
#全探索余裕 桁は多くて40程度なので
for b in range(2, sqrt(n) + 1):
  if digitsum(b, n) == s:
    print(b)
    exit(0)
#√nより大きいなら
#b^2 > n である。２桁ということ
#2桁目がpなら、1桁目はs-pである
#pb + s - p = n
#b = (n - s) // p + 1
for p in range(sqrt(n), 0, -1):
  b = (n - s) // p + 1
  if b <= 1: continue
  if digitsum(b, n) == s:
    print((n - s) // p + 1)
    exit(0)
print(-1)

Submission status: Accepted

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

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

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

sqrt_n = math.floor(math.sqrt(n))
for b in range(2, sqrt_n + 1):
    if f(b, n) == s:
        print(b)
        sys.exit()
for p in range(1, sqrt_n + 1):
    p_sum= sqrt_n + 1 - p
    b = int( (n -s)/p_sum ) + 1
    if b >= 2 and f(b, n) == s:
        print(b)
        sys.exit()
print('-1')

Submission status: Accepted

Solution code:
import sys
n=int(input())
s=int(input())
if n==s:
  print(n+1)
  sys.exit()
if n<s:
  print(-1)
  sys.exit()
for i in range(2,int(n**0.5)+1):
  ct=0;x=n;b=i
  while x>=b:
    ct+=x%b
    x=x//b
  ct+=x
  if ct==s:
    print(b)
    sys.exit()
for i in range(int(n**0.5),0,-1):
  if (n-s)%i==0:
    ct=0;x=n;b=(n-s)//i+1
    while x>=b:
      ct+=x%b
      x=x//b
    ct+=x
    if ct==s:
      print(b)
      sys.exit()
print(-1)

Submission status: Accepted

Solution code:
n = int(input())
s = int(input())
def sub(n, b):
  r = 0
  while n > 0:
    r += n%b
    n = n//b
  return r
if s > n:
  print(-1)
  exit()
if s == n:
  b = n+1
  print(b)
  exit()
for b in range(2, n+1):
  if b*b > n:
    break
  s2 = sub(n, b)
  if s2 == s:
    print(b)
    exit()
bs = []
for p in range(1, n+1):
  if p*p > n:
    break
  if (n-s)%p == 0:
    b = (n-s)//p+1
    bs.append(b)
bs.sort()
for b in bs:
  s2 = sub(n, b)
  if s2 == s:
    print(b)
    exit()
print(-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC44 D

import sys
import math
import bisect
import time
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

#√n < bの場合はnをb進数表記すると2桁になることに着目
n = I()
s = I()
def f(b,n):
    if n < b:
        return n
    else:
        return f(b,n//b) + n % b

if n == s:
    print(n+1)
    quit()
for b in range(2,int(math.sqrt(n))+1):
    if f(b,n) == s:
        print(b)
        quit()
for p in range(1,int(math.sqrt(n))+1)[::-1]:
    b = (n-s)//p + 1
    if b <= 1:
        continue
    if f(b,n) == s:
        print(b)
        quit()
print(-1)

Submission status: Accepted

Solution code:
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(n**(1/2))+1):
  m=n
  wa=0
  while m>0:
    wa+=m%b
    m=m//b
  if wa==s:
    print(b)
    exit()

for p in range(int((n-1)**(1/2)),0,-1):
  if (n-s)%p==0:
    b=(n-s)//p+1
    if p+n%b==s:
      print(b)
      exit()
print(-1)