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: Time Limit Exceeded

Solution code:
from sys import exit
from itertools import combinations

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

def pfact(x):
  res = []
  while x > 1:
    for p in range(2, int((x+1)**0.5+1)):
      if x % p == 0:
        res.append(p)
        x //= p
        break
    else:
      res.append(x)
      break
  return res

def prod(xs):
  res = 1
  for x in xs:
    res *= x
  return res

def divisors(n):
  primes = pfact(n)
  res = []
  for r in range(len(primes)+1):
    for sub in combinations(primes, r):
      res.append(prod(sub))
  return sorted(set(res))

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

n = read()
s = read()

# n == s mod (b-1) なので、
# (b-1) は (n-s) の約数

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

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

for x in divisors(abs(n-s)):
  b = x + 1
  # print(b)
  if f(b, n) == s:
    print(b); exit()
    # pass

print(-1)

Submission status: Accepted

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

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

def main():
    n = int(input())
    s = int(input())
    
    ans = -1
    if n == s:
        ans = n + 1
    else:
        for b in range(2, int(n**0.5) + 1):
            if digit_sum(n, b) == s:
                ans = b
                break
        
        else:
            for p in range(1, int(n**0.5)+1):
                b = (n - s) // p + 1
                if b >= 2 and digit_sum(n, b) == s:
                    if ans == -1:
                        ans = b
                    else:
                        ans = min(ans, b)
                
                if b >= 1 and digit_sum(n, b+1) == s:
                    if ans == -1:
                        ans = b+1
                    else:
                        ans = min(ans, b+1)

    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

def main():
    n = int(input())
    s = int(input())
    ans = -1

    if n < s:
        ans = -1

    elif n == s:
        ans = n + 1

    else:
        key = []
        start, first = n, 1

        for i in range(1, n):
            first = digit_sum(n, start)
            end = start - n // i // (i + 1)
            if start == end+1:
                judge = start
                break

            while end > 1:
                if digit_sum(n, end) == i * (start - end) + first:
                    end -= 1
                    continue
                break
            next_start = end
            value = digit_sum(n, start)
            end = value + (start - end - 1) * i
            key.append((start, value, end, i, first))
            judge = start
            start = next_start
            if start == 1:
                break

        for i in range(2, judge + 1):
            sub = digit_sum(n, i)
            if sub == s:
                ans = i
                break
        else:
            for index, start, end, i, first in reversed(key):
                if end < s or s < start:
                    continue
                if (s - start) % i:
                    continue
                ans = index - (s - first) // i
                break

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def F(n, b):
    res = 0
    while n:
        n, m = divmod(n, b)
        res += m
    return res


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


inf = 10**18
ans = inf
d = 0
while True:
    d += 1
    lower = N // d
    upper = N // (d + 1) + 1
    if lower == upper:
        break
    FL = F(N, lower)
    FU = F(N, upper)
    if FL <= S <= FU:
        if (FU - S) % d == 0:
            pos = (FU - S)//d
            ans = min(ans, upper + pos)

for b in range(2, upper + 1):
    if F(N, b) == S:
        ans = min(ans, b)

if ans >= inf:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = int(input())
if(n<s):
    print(-1)
    exit()
elif(n==s):
    print(n+1)
    exit()

lim = 10**6
for i in range(2,lim+1):
    tmp = 0
    x = n
    while(x > 0):
        tmp += x%i
        x //= i
    if(tmp==s):
        print(i)
        exit()

#2桁
ns = n-s
inf = 10**12
ans = inf
for i in range(1,ns+1):
    if(i**2 > ns):
        break

    if(ns%i==0):
        b = ns//i + 1
        y = n-(b*i)
        if(i+y==s)&(0<=y<b):
            ans = min(ans,b)

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

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
s = int(input())
def sub(n, b):
    """nのb進数表記したときの各桁
    n = sum(pow(b,i) * ans[i])
    """
    ans = []
    while n>0:
        n,v = divmod(n, b)
        ans.append(v)
    return ans
ans = None
for b in range(2,n+1):
    if b**2>n:
        break
    if sum(sub(n, b))==s:
        ans = b
        break
if ans is None:
    ans = float("inf")
    if n==s:
        ans = s+1
    for p in range(1,n+1):
        if p**2>n:
            break
        if (n+p-s)%p==0:
            b = (n+p-s)//p
            q = s - p
            if b**2>n and 0<=q<b and p<b and b*p+q==n and p+q==s:
                ans = min(ans, b)
            else:
                continue
if ans is None or ans==float("inf"):
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,s = map(int,read().split())

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

M = 4*10**5

ans = -1
for i in range(2,M):
    if f(i,n) == s:
        print(i)
        break
else:
    for x in range(M,0,-1):
        if (n-s)%x==0:
            b = (n-s)//x + 1
            #print(b)
            if x < b and 0 <= s-x < b:
                print(b)
                break
    else:
        if n==s:
            print(n+1)
        else:
            print(-1)

Submission status: Accepted

Solution code:
import sys

MAX = 1000000


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


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

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

    ans = -1

    for b in range(2, min(n + 1, MAX) + 1):
        sm = digit_sum(n, b)
        if sm == s:
            ans = b
            break

    if ans != -1:
        print(ans)
        sys.exit()

    if n + 1 <= MAX:
        print(-1)
        sys.exit()

    for p in reversed(range(1, MAX)):
        if (n - s) % p != 0:
            continue
        b = (n - s) // p + 1
        if b < 2:
            continue
        sm = digit_sum(n, b)
        if sm == s:
            ans = b
            break

    if ans != -1:
        print(ans)
        sys.exit()

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

    print(-1)

Submission status: Accepted

Solution code:
import sys

MAX = 1000000


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


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

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

    ans = -1

    for b in range(2, min(n + 1, MAX) + 1):
        sm = digit_sum(n, b)
        if sm == s:
            ans = b
            break

    if ans != -1:
        print(ans)
        sys.exit()

    if n + 1 <= MAX:
        print(-1)
        sys.exit()

    for p in reversed(range(1, MAX)):
        if (n - s) % p != 0:
            continue
        b = (n - s) // p + 1
        if b < 2:
            continue
        sm = digit_sum(n, b)
        if sm == s:
            ans = b
            break

    if ans != -1:
        print(ans)
        sys.exit()

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

    print(-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import sqrt

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

def divisors(M):#Mの約数列 O(n^(0.5+e))
    import math
    d=[]
    i=1
    while math.sqrt(M)>=i:
        if M%i==0:
            d.append(i)
            if i**2!=M:
                d.append(M//i)
        i=i+1
    d.sort()
    return d

n=int(input());s=int(input())
if 0>n-s:
    print(-1)
else:
    m=int(sqrt(n))
    for b in range(2,m+1):
        if digitsum(b,n)==s:
            print(b)
            break
    else:
        d=divisors(n-s)
        for i in d:
            if i>=m and s>=(n-s)//i and i+1>(s-(n-s)//i):
                print(i+1)
                break
        else:
            if n==s:
                print(n+1)
            else:
                print(-1)

Submission status: Accepted

Solution code:
n = int(input())
s = int(input())
if n == s:
    print(n + 1)
    exit()

m = abs(n-s)

a = set()
i = 1
while i * i <= m:
    if m % i == 0:
        a.add(i)
        a.add(m // i)
    i += 1

for i in sorted(list(a)):
    i += 1
    su = 0
    nn = n
    while nn:
        su += nn % i
        nn //= i
    if su == s:
        print(i)
        break
else:
    print(-1)

Submission status: Accepted

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

Submission status: Accepted

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

def tt(k, N):
    r = 0
    while N:
        N, m = divmod(N, k)
        r += m
#    print(k, r)
    return r

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

for i in range(2, math.floor(N**0.5) + 2):
    if tt(i, N) == S:
        print(i)
        sys.exit()

for k in range(math.floor(N**0.5), 0, -1):
    s = N//k
    f = N//(k+1) + 1
    si = k + N%k
    fi = si + (s-f)*k
    if N//(s**2) > 0:
        continue
#    print("aaa", k, si, fi, s, f)
    if si <= S <= fi and ((fi-S) % k == 0):
#        print(k)
#        print("cc", f, fi, S, f+(fi-S)//k)
        print(f+(fi-S)//k)
        sys.exit()
#    for i in range(f, s+1):
#        tt(i, N)
#        if ( i == f or i == s ) and S == tt(i, N):
#            print(i)
#            sys.exit()

print(-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 math


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

def main():
    n=int(input())
    s=int(input())
    if n == s:
        return n+1
    elif s > (n+1)//2:
        return -1
    else:
        rn = math.floor(math.sqrt(n))
        for i in range(2,rn+1):
            if dsum(i,n) == s:
                return i
        for i in range(rn,0,-1):
            if (n-s) % i == 0:
                b = (n-s)//i+1
                if dsum(b,n) == s:
                    return b
        return -1



print(main())

Submission status: Accepted

Solution code:
import math

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

def f(B, N):
    X, res = N, 0
    while 0 < X:
        res += X % B
        X //= B
    return res


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

i = 2
while i * i <= N:
    if f(i, N) == S:
        print(i)
        exit()
    i += 1

sqrtN = math.floor(math.sqrt(N))
i = 1
ans = -1
while i * i < N:
    if (N - S) % i != 0:
        i += 1
        continue
    b = (N - S) // i + 1
    if sqrtN < b and f(b, N) == S:
        ans = b
    i += 1

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

Submission status: Accepted

Solution code:
import math

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

def f(B, N):
    X, res = N, 0
    while 0 < X:
        res += X % B
        X //= B
    return res


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

i = 2
while i * i <= N:
    if f(i, N) == S:
        print(i)
        exit()
    i += 1

sqrtN = math.floor(math.sqrt(N))
i = 1
ans = []
while i * i < N:
    if (N - S) % i != 0:
        i += 1
        continue
    b = (N - S) // i + 1
    if sqrtN < b and f(b, N) == S:
        ans.append(b)
    i += 1

print(-1 if len(ans) == 0 else min(ans))

Submission status: Accepted

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

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def f(n,b):
        if n < b:
            return n
        return f(n//b, b)+(n%b)
    n,s = IR(2)
    if n == s:
        print(n+1)
        return
    for b in range(2,10**6+2):
        if f(n,b) == s:
            print(b)
            return
    if n <= 10**6:
        print(-1)
        return
    N = 10**6+1
    for i in range(1,N)[::-1]:
        l = (n//(i+1))+1
        r = (n//i)+1
        while r-l > 1:
            m = (l+r) >> 1
            fx = f(n,m)
            if fx >= s:
                l = m
            else:
                r = m
        if f(n,l) == s:
            print(l)
            return
    print(-1)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

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

    def check(a, i):
        ans = 0
        while a:
            ans += a % i
            a //= i
        return ans

    for i in range(2, int(n**0.5)+2):
        if check(n, i) == s:
            print(i)
            return 0
    for i in range(int(n**0.5), 0, -1):
        if (n-s) % i == 0:
            b = (n-s)//i+1
            x = s-i
            if x < 0:
                continue
            if b > x:
                print(b)
                return 0
    if n == s:
        print(n+1)
    else:
        print(-1)


main()

Submission status: Accepted

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

ans = 10**13
for k in range(1, int(n**0.5) + 3):
    if (n-s) % k != 0 or n-s < 0:
        continue
    b = (n-s)//k + 1
    if b == 1:
        continue
    if f(b, n) == s:
        ans = min(b, ans)

if ans != 10**13:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
import math
import sys
n=int(input())
s=int(input())
root=int(math.ceil(math.sqrt(n)))

buf=10**12
if s==n:
    print(n+1)
    sys.exit()
for i in range(1,root):
    res=s-i
    x=(n-res)//i
    if x*i+res==n and x>1 and x>res and res>=0:
        #print(x,i,res,s,n)
        buf=min(buf,x)
#print(buf)
for i in range(2,root+1):
    count=0
    b=n
    while(b!=0):
        count+=b%i
        b=b//i
    if count==s:
        buf=i
        break
print(buf if buf!=10**12 else -1)

Submission status: Accepted

Solution code:
import math

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

if n == 1:
    if s == 1:
        print(2)
    else:
        print(-1)
    exit()

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

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


def ds(N, b):
    ret = 0
    while True:
        N, mod = divmod(N, b)
        ret += mod
        if N == 0:
            return ret


i = 0
for i in range(2, math.floor(n**(1/2)) + 1):
    if ds(n, i) == s:
        print(i)
        exit()

if i == 0:
    i = math.floor(n**(1/2))
c = n // (i + 1)
for i in range(c, 0, -1):
    if (n-s) % i == 0:
        b = (n-s)//i + 1
        if i < b and 0 <= s-i < b:
            print(b)
            exit()

print(-1)

Submission status: Accepted

Solution code:
import math

N = int(input())
S = int(input())
L = N-S

def search(b, n=N):
    ans = 0
    while n >= b:
        ans += n%b
        n //= b
    ans += n
    return ans


def main():

    if L < 0:
        print(-1)
    elif L == 0:
        print(N+1)
    else:
        P = []
        for l in range(1, int(math.sqrt(L))+2):
            if L%l == 0:
                P.append(l+1)
                P.append(L//l+1)
        P.sort()

        ans = -1
        for p in P:
            if p == 1: continue
            S0 = search(p)
            if S == S0:
                ans = p
                break

        print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

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

ans = float('inf')

for b in range(1, int(N**0.5) + 100):
    if b > 1 and f(b, N) == S:
        ans = min(ans, b)

    q = S - b
    b = (N - q) // b
    if b > 1 and f(b, N) == S:
        ans = min(ans, b)

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

Submission status: Accepted

Solution code:
import math
n = int(input())
s = int(input())
def solve(n, s):
    if n == s:
        return n+1
    for b in range(2, math.floor(n**0.5)+1):
        tmp = n
        res = 0
        while tmp>=b:
            res+=tmp%b
            tmp //=b
        res += tmp
        if res == s:
            return b
    for p in range(int(n**0.5), 0, -1):
        r = s-p
        if r<0:
            continue
        if (n-r)%p == 0:
            b = (n-r)//p
            if r<b and b*b>n:
                return b
    return -1
print(solve(n, s))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import sqrt, factorial
from sys import setrecursionlimit
setrecursionlimit(10000000)

def inpl(): return list(map(int, input().split()))
N = int(input())
S = int(input())

RN = int(sqrt(N)) + 1
RN += ((RN+1)**2 == N)

def func(b, N):
    if b <= 1:
        return -1
    tmp = 0
    while N:
        N, d = divmod(N, b)
        tmp += d
    return tmp

for b in range(2, RN+1):
    tmp = func(b, N)
    if tmp == S:
        print(b)
        break
else:
    for x in range(RN, 0, -1):
        b = (N-S+x)//x
        if func(b, N) == S:
            print(b)
            break
    else:
        if func(S+1, N) == S:
            print(S+1)
        else:
            print(-1)

Submission status: Accepted

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

sqrt = 0
for i in range(n+1):
    if i*i >= n:
        sqrt = i
        break

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


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

# b = 2 ~ sqrt
# 少し先を見てもいい
for b in range(2, sqrt+1):
    use_n = n
    ans_tmp = dsum(n, b)
    if ans_tmp == s:
        print(b)
        exit()

# n = p*b + q
# s = p + q
# n = 2, s = 1 なら、 b=2, p=1, q=0
for p in range(1, sqrt)[::-1]:
    b = (n-s)//p + 1
    if b > 1 and dsum(n, b) == s:
        print(b)
        exit()
print(-1)

Submission status: Accepted

Solution code:
n=int(input())
s=int(input())
def fun(b,n):
    if n<b:
        return n
    else:
        return fun(b,n//b)+n%b
if n<s:
    print(-1)
elif n==s:
    print(n+1)
else:
    for b in range(2,int(n**0.5)+1):
        if fun(b,n)==s:
            print(b)
            exit()
    yaku=set()
    for x in range(1,int((n-s)**0.5)+1):
        if (n-s)%x==0:
            yaku|={x,(n-s)//x}
    ans=n+2
    for k in yaku:
        b=(n-s)//k+1
        l=s-k
        if 0<=l<b and n<b**2 and k+l==s:
            ans=min(ans,b)
    if ans>n:
        print(-1)
    else:
        print(ans)

Submission status: Accepted

Solution code:
def f(b, n):
    if n < b:
        return n
    else:
        q, r = divmod(n, b)
        return f(b, q) + r

n = int(input())
s = int(input())
if n == s:
    print(n+1)
else:
    b = 2
    while b*b <= n:
        if f(b, n) == s:
            print(b)
            break
        b += 1
    else:
        p = 1
        ans = 10**13
        while p*p <= n:
            b = (n - s) // p + 1
            if p < b and s - p < b and f(b, n) == s:
                ans = min(ans, b)
            p += 1
        if ans == 10**13:
            print(-1)
        else:
            print(ans)

Submission status: Accepted

Solution code:
import math


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


def main():
    n = int(input())
    s = int(input())
    if s == n:
        print(n+1)
        return
    elif s > n:
        print(-1)
        return
    sqrt = int(math.sqrt(n))
    for b in range(2, sqrt+2):
        if f(b, n) == s:
            print(b)
            return
    for x in range(sqrt, 0, -1):
        if x > s:
            continue
        y = s - x
        b = (n - y) // x
        if b >= 2 and (n - y) % x == 0 and f(b, n) == s:
            print(b)
            return
    print(-1)


if __name__ == "__main__":
    main()

Submission status: Accepted

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


def prime_decomposition(n):
    i = 2
    ret = collections.defaultdict(int)
    while i * i <= n:
        while n % i == 0:
            n //= i
            ret[i] += 1
        i += 1
    if n > 1:
        ret[n] = 1
    return ret


def digitsum(x, f):
    if x < f:
        return x
    else:
        return x % f + digitsum(x // f, f)


if N == S:
    print(N + 1)
    exit()
fs_dict = prime_decomposition(N - S)
fs_set = set([1])
for p, n in fs_dict.items():
    fs_set_copy = fs_set.copy()
    for i in range(1, n + 1):
        for x in fs_set_copy:
            fs_set.add(x * p**i)
for f in sorted(fs_set):
    f += 1
    if digitsum(N, f) == S:
        print(f)
        exit()
print(-1)

Submission status: Accepted

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

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


def prime_decomposition(n):
    i = 2
    ret = collections.defaultdict(int)
    while i * i <= n:
        while n % i == 0:
            n //= i
            ret[i] += 1
        i += 1
    if n > 1:
        ret[n] = 1
    return ret


def digitsum(x, f):
    if x < f:
        return x
    else:
        return x % f + digitsum(x // f, f)


fs_dict = prime_decomposition(N - S)
fs_set = set([1])

for p, n in fs_dict.items():
    fs_set_copy = fs_set.copy()
    for i in range(1, n + 1):
        for x in fs_set_copy:
            fs_set.add(x * p**i)
for f in sorted(fs_set):
    f += 1
    if digitsum(N, f) == S:
        print(f)
        exit()
else:
    print(-1)

Submission status: Accepted

Solution code:

import math


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

    return n, s


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


def submit():
    n, s = read_input()
    sqrtn = math.ceil(math.sqrt(n))

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

    for i in range(2, sqrtn + 1):
        if f(i, n) == s:
            print(i)
            return

    for i in range(sqrtn - 1, 0, -1):
        p = i
        q = s - p
        sho,mod = divmod(n - q, p)
        if mod == 0:
            b = sho
        else:
            continue

        if q < b and p < b:
            if f(b, n) == s:
                print(b)
                return

    print(-1)

if __name__ == '__main__':
    submit()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


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


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

    if s == n:
        return n+1

    b = 2
    while b * b <= n:
        if f(n, b) == s:
            return b
        b += 1
    
    for p in range(b-1, 0, -1):
        if (n - s) % p > 0:
            continue

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


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
    print(solve(n, s))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

if s == n:
    print(n+1)
    exit()
for i in range(2, int(n**0.5) + 1):
    if(f(i, n) == s):
        print(i)
        exit()
ans = 10**15
for i in range(1, int(n**0.5) + 1):
    b = (n-s) // i + 1
    if b < 2:
        continue
    if f(b, n) == s:
        ans = min(ans, b)

if ans == 10**15:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import numpy as np
def f(b, n):
    s = 0
    while n > 0:
        s += n % b
        n //= b
    return s

INF = 10**15
def solve(n, s):
    if n == s:
        return n+1
    m = int(np.sqrt(n)) + 1
    for b in range(2, m+1):
        if f(b, n) == s:
            return b
    best = INF
    for p in range(1, m+10):
        q = s - p
        b = (n - q) // p
        if (b > p) and (b > q) and (f(b, n) == s):
            best = min(best, b)
    return -1 if (best == INF) else best

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

Submission status: Accepted

Solution code:
import itertools
import math 
 
n,s = [int(input()) for _ in range(2)]
 
def n_base_sum(n,b):
    if(math.floor(n/b)):
        return n_base_sum(math.floor(n/b),b)+n%b
    else:
        return n%b
 
def search_p(n,s):
    for p in range(math.floor(math.sqrt(n))+1,0,-1):
        b = (n-s)//p + 1
        if b >1 :
            q = n % b
            if p+q ==s and q < b and n == p*b+q and p<b:
                return b
        
    return -1
 
ans =-1
flag = False
answers = []
if s == n:
    ans = n+1
    flag =True
    answers.append(ans)
for b in  range(2,math.ceil(math.sqrt(n))+1):
    if s== n_base_sum(n,b):
        ans = b
        flag = True
        answers.append(ans)
        break
ans = search_p(n,s)
if ans != -1:
    flag =True
    answers.append(ans)
 
if not flag:
    print(-1)
else:
    print(int(min(answers)))

Submission status: Accepted

Solution code:
def f(_b, _n):
    ret = 0
    while _n > 0:
        ret += _n % _b
        _n = _n // _b
    return ret
INF = 10 ** 12

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

ans = INF
if n >= s:
    max_digits = len(str(bin(n))) - 2
    # 3桁まで
    for k in range(max_digits, 2, -1):
        min_b = max(2, -(int(- (n ** (1 / k)))))
        max_b = int((n - s + 1) ** (1 / (k - 1)))
        for b in range(min_b, max_b + 1, 1):
            if f(b, n) == s:
                ans = b
                break
        if ans != INF:
            break

    if ans == INF:
        # 2桁
        for a1 in range(1, s + 1):
            if (n - s) < (a1 - 1) * a1:
                break
            if (n - s) % a1 == 0:
                a0 = s - a1
                b = (n - a0) // a1
                if a0 < b and a1 < b and (b * a1) == (n - a0) and b < ans:
                    ans = b

    if ans == INF:
        # 1桁
        if n == s:
            ans = n + 1
if ans == INF:
    ans = -1

print(ans)

Submission status: Accepted

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

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

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

is_b = False
if n < s:
  print(-1)
elif n == s:
  print(n + 1)
else:
  b = 2
  is_b = False
  while b * b <= n:
    if s == f(b, n):
      is_b = True
      break
    b += 1
  if is_b:
    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:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# 解説PDFの通りに実装
#
# 途中まで全探索、途中までは2桁の場合のみ考えればよい
# ことに自力では気付けなかった

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys


def get_sum(base, n):
    nums = []
    while n > 0:
        nums.append(n % base)
        n //= base
    return sum(nums)


def solve(N, S):
    if S == N:
        return S + 1
    for base in range(2, int(math.sqrt(N)) + 2):
        if S == get_sum(base, N):
            return base
    for p in range(int(math.sqrt(N)) + 1, 0, -1):
        q = S - p
        if (N - q) % p == 0:
            base = (N - q) // p
            if base <= 1 or q < 0 or q >= base:
                continue
            return base
    return -1


N = int(input())
S = int(input())
print(solve(N, S))

Submission status: Accepted

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

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

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

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

ans = 10**18

for x in range(1, int(math.sqrt(n)+10)):
    y = s - x
    b = (n-s)//x+1
    if x < b and y < b and f(b, n) == s:
        ans = min(ans, b)
if ans == 10**18:
    ans = -1
print(ans)