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: Runtime Error

Solution code:
# seishin.py
from math import sqrt
n, s = map(int, open(0).read().split())

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

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

# 2 <= b <= sqrt(n)
for b in range(2, int(sqrt(n))+1):
    if f(b, n) == s:
        print(b)
        exit(0)

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

Submission status: Runtime Error

Solution code:
def d_DigitSum(N, S):
    if S == N:
        # f(b,N)=Nを満たすbはN+1が最小
        return N + 1

    from math import sqrt, floor

    def f(b, n):
        if n < b:
            return n
        else:
            return f(b, floor(n / b)) + n % b
    sq = floor(sqrt(N))
    # 2<=b<=√Nまで探索
    for b in range(2, sq + 1):
        if f(b, N) == S:
            return b
    # √N<=b<=Nまで探索
    for p in range(1, sq):
        b = (N - S) // p + 1
        if f(b, N) == S:
            return b
    return -1
N = int(input())
S = int(input())
print(d_DigitSum(N, S))

Submission status: Runtime Error

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

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

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

sn = math.ceil(math.sqrt(n))
for i in range(2, sn):
    if f(i, n) == s:
        print(i)
        sys.exit(0)

for i in range(1, sn):
    if (n - s) % i == 0:
        b = (n-s)//i + 1
        if f(b + n%b, n) == s:
            print(b)
            sys.exit(0)
if s == n:
    print(n+1)
else:
    print(-1)

Submission status: Runtime Error

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

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

if s > n:
    print(-1)

sn = math.ceil(math.sqrt(n))
for i in range(2, sn):
    if f(i, n) == s:
        print(i)
        sys.exit(0)

for i in range(1, sn):
    if (n - s) % i == 0:
        b = (n-s)//i + 1
        if 1 + n % b == s and b + n % b == n:
            print(b)
            sys.exit(0)
if s == n:
    print(n)
else:
    print(-1)

Submission status: Runtime Error

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

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

sn = math.ceil(math.sqrt(n))
for i in range(2, sn):
    if f(i, n) == s:
        print(i)
        sys.exit(0)

for i in range(1, sn):
    if (n - s) % i == 0:
        b = (n-s)//i + 1
        if 1 + n % b == s and b + n % b == n:
            print(b)
            sys.exit(0)
print(-1)

Submission status: Runtime Error

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

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

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

sn = math.ceil(math.sqrt(n))
for i in range(2, sn):
    if f(i, n) == s:
        print(i)
        sys.exit(0)

for i in range(1, sn):
    if (n - s) % i == 0:
        b = (n-s)//i + 1
        if 1 + n % b == s:
            print(b)
            sys.exit(0)
print(-1)

Submission status: Runtime Error

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

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

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

sn = math.ceil(math.sqrt(n))
for i in range(2, sn):
    if f(i, n) == s:
        print(i)
        sys.exit(0)

for i in range(1, sn):
    if (n - s) % i == 0:
        b = (n-s)//i + 1
        if b + n % b == s:
            print(b)
            sys.exit(0)
print(-1)

Submission status: Runtime Error

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

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

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

res = -1

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

for b in range(2, int(sqrt(n))+2):
  if f(b, n) == s:
    res = b
    break

print(res)

Submission status: Runtime Error

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

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

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

res = -1

for p in range(1, int(sqrt(n))+1):
  b = (n-s)//p + 1
  if f(b, n) == s:
    res = b
    break

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

print(res)

Submission status: Runtime Error

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

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

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

res = -1

for p in range(1, int(sqrt(n))+1):
  b = (n-s)//p + 1
  if f(b, n) == s:
    res = b
    break

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

print(res)

Submission status: Runtime Error

Solution code:
import sys
import math

sys.setrecursionlimit(100000000)

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

Submission status: Runtime Error

Solution code:
import sys
import math

sys.setrecursionlimit(100000000)

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

Submission status: Runtime Error

Solution code:

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

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

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

print(-1)

Submission status: Runtime Error

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


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

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

Submission status: Runtime Error

Solution code:
x, y = map(int, raw_input().split())
def sumdigit(b=x, n=y):
    if n < b:
        return n
    else:
        return sumdigit(b, n//b) + n%b

print sumdigit(x, y)

Submission status: Runtime Error

Solution code:
x, y = map(int, raw_input().split())
def sumdigit(b=x, n=y):
    if n < b:
        return n
    else:
        return sumdigit(b, n/b ) + n%b

print sumdigit(x, y)

Submission status: Runtime Error

Solution code:
import math
x, y = map(int, raw_input().split())


def sumdigit(b=x, n=y):
    if n < b:
        return n
    else:
        return sumdigit(b, math.floor(n/b)) + n%b

print sumdigit(x, y)

Submission status: Runtime Error

Solution code:
class nnDigitSum:
	def dfs(self,b,n):
		if n<b:
			return n
		return self.dfs(b,n/b)+n%b
	def returnMinimumB(self,n,s):
		i=2
		while i*i<=n:
			if self.dfs(i,n)==s: return i
			i+=1
		cands=[]
		i=1
		while i*i<=n-2:
			if not (n-s)%i: cands.append((n-s)/i+1)
			i+=1
		cands=sorted(cands)
		for cand in cands:
			if self.dfs(cand,n)==s: return cand
		if n==s:
			return n+1
		elif s==1:
			return n
		return -1
if __name__ == "__main__":
	N = int(raw_input())
	s = int(raw_input())
	d = nnDigitSum()
	print d.returnMinimumB(N,s)