Problem:


Score : 500 points

Problem Statement

For integers b (b \geq 2) and n (n \geq 1), let the function f(b,n) be defined as follows:

f(b,n) = n, when n < b

f(b,n) = f(b,\,{\rm floor}(n / b)) + (n \ {\rm mod} \ b), when n \geq b

Here, {\rm floor}(n / b) denotes the largest integer not exceeding n / b,
and n \ {\rm mod} \ b denotes the remainder of n divided by b.

Less formally, f(b,n) is equal to the sum of the digits of n written in base b.
For example, the following hold:

f(10,\,87654)=8+7+6+5+4=30

f(100,\,87654)=8+76+54=138

You are given integers n and s.
Determine if there exists an integer b (b \geq 2) such that f(b,n)=s.
If the answer is positive, also find the smallest such b.

Constraints

1 \leq n \leq 10^{11}

1 \leq s \leq 10^{11}

n,\,s are integers.

Input

The input is given from Standard Input in the following format:

n
s

Output

If there exists an integer b (b \geq 2) such that f(b,n)=s, print the smallest such b.
If such b does not exist, print -1 instead.

Sample Input 1

87654
30

Sample Output 1

10

Sample Input 2

87654
138

Sample Output 2

100

Sample Input 3

87654
45678

Sample Output 3

-1

Sample Input 4

31415926535
1

Sample Output 4

31415926535

Sample Input 5

1
31415926535

Sample Output 5

-1



Sample input:
87654
30


Sample output:
10

Submission status: Wrong Answer

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

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

if s == n :
    print(n+1)
elif s > n :
    print(-1)
else :
    flag = False
    b = 2
    while b * b < n :
        if f(b, n) == s :
            print(b)
            flag = True
            break
        b += 1
            
    if not flag :
        p = int(n ** 0.5 - 1)
        while p > 0 :
            if (n - s) % p == 0 :
                b = 1 + (n - s) // p
                if p < b and 0 <= s - p < b :
                    print(b)
                    flag = True
                    break
                
            p -= 1
        
    if not flag :
        print(-1)

Submission status: Wrong Answer

Solution code:
import bisect
import heapq
import itertools
import math
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, S = [int(sys.stdin.readline()) for _ in range(2)]


@lru_cache(maxsize=None)
def f(b, n):
    if n < b:
        return n
    return f(b, int(n // b)) + n % b


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


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

# #########
# b = 2
# ans = -1
# prev = 0
# while b <= N:
#     if f(b, N) > prev:
#         print(b, N, f(b, N))
#     prev = f(b, N)
#     b += 1
# ##########

b = 2
ans = -1
while b <= math.sqrt(N) + 1:
    if f(b, N) == S:
        ans = b
        break
    b += 1
if ans >= 0:
    print(ans)
    exit()

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

Submission status: Wrong Answer

Solution code:
import math
import sys
sys.setrecursionlimit(10**5)
n = int(input())
s = int(input())

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

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

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

if n == 1:
    print (-1)
    exit()

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

for p in range(1, int(math.sqrt(n))+2):
    b = (n-s)//p + 1
    # print (b)
    if b != 1 and f(b, n) == s:
        print (b)
        exit()
print (-1)

# for i in range(2, 11):
#     print (i, f(i,10))

Submission status: Wrong Answer

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

n=int(input())
s=int(input())
if s>n:
  print(-1)
elif s==n:
  print(n+1)
else:
  ans=10**18
  for i in range(2,int(n**0.5)+1):
    if f(i,n)==s:
      ans=i
      break
  if ans!=0:
    print(ans)
  else:
    for i in range(1,int(n**0.5)+1):
      tb=(n-s)//i+1
      if tb==1:
        continue
      if f(tb,n)==s:
        ans=min(ans,tb)
    if ans!=0:
      print(ans)
    else:
      print(-1)

Submission status: Wrong Answer

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

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

n=int(input())
s=int(input())
if s>n:
  print(-1)
elif s==n:
  print(n+1)
else:
  ans=10**18
  for i in range(2,int(n**0.5)+1):
    if f(i,n)==s:
      ans=i
      break
  else:
    for i in range(1,int(n**0.5)+1):
      tb=(n-s)//i+1
      if tb==1:
        continue
      if f(tb,n)==s:
        ans=min(ans,tb)
    if ans!=0:
      print(ans)
    else:
      print(-1)

Submission status: Wrong Answer

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

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

n=int(input())
s=int(input())
if s>n:
  print(-1)
elif s==n:
  print(n+1)
else:
  ans=0
  for i in range(2,int(n**0.5)+1):
    if f(i,n)==s:
      ans=i
      break
  if ans!=0:
    print(ans)  
  else:
    for i in range(1,int(n**0.5)+1):
      tb=(n-s)//i+1
      if tb==1:
        continue
      if f(tb,n)==s:
        ans=tb
        break
    if ans!=0:
      print(ans)
    else:
      print(-1)

Submission status: Wrong Answer

Solution code:
n, = list(map(int,input().split()))
s, = list(map(int,input().split()))
if s==n:
  print(n+1)
elif s==1:
  print(n)
else:
  r = -1
  for b in range(2,n+1):
    c = 0
    m = n
    while m>0:
      c += m % b
      m //= b
    if c==s:
      r=b
      break
  print(r)

Submission status: Wrong Answer

Solution code:
n, = list(map(int,input().split()))
s, = list(map(int,input().split()))
if s==n:
  print(n+1)
elif s==1:
  print(n)
else:
  r = -1
  for b in range(2,n+1):
    if b*b>n:
      break
    c = 0
    m = n
    while m>0:
      c += m % b
      m //= b
    if c==s:
      r=b
      break
  print(r)

Submission status: Wrong Answer

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 == 1 and n == 1:
        print(-1)
        return
    elif s == 1:
        print(n)
        return
    elif 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: Wrong Answer

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 == 1 and n == 1:
        print(-1)
        return
    elif s == 1:
        print(n)
        return
    elif 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
        if (n - y) % x != 0 or (b - y) < x:
            continue
        b = (n - y) // x
        if f(b, n) == s:
            print(b)
            return
    print(-1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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 == 1:
        if n == 1:
            print(-1)
        else:
            print(n)
        return
    elif 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 s < x:
            continue
        y = s - x
        if (n - y) % x != 0 and (b - y) < x:
            continue
        b = (n - y) // x
        if f(b, n) == s:
            print(b)
            return
    print(-1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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 == 1:
        print(n)
        return
    elif 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 s < x:
            continue
        y = s - x
        if (n - y) % x != 0 and (b - y) < x:
            continue
        b = (n - y) // x
        if f(b, n) == s:
            print(b)
            return
    print(-1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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 == 1:
        print(n)
        return
    elif s == n:
        print(n+1)
        return
    elif s > n:
        print(-1)
        return
    sqrt = -int(-math.sqrt(n))
    b = 2
    for b in range(2, sqrt+1):
        if f(b, n) == s:
            print(b)
            return
    for x in range(sqrt, s, -1):
        y = s - x
        z = n - x
        b = z // y
        if z % y == 0 and b > 0 and f(b, n) == s:
            print(b)
            return
    print(-1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#http://arc060.contest.atcoder.jp/data/arc/060/editorial.pdf
def Base_10_to_n(n,x):
    ret = 0
    while n > 0:
      ret += n%x
      n //= x
    return ret

def solve():
  n = int(input())
  s = int(input())
  ans = 10**15
  if s == n :
    print(n+1)
    exit()
  elif n < s :
    print(-1)
    exit()
  else:
    upper = int(pow(n, 0.5))
    for i in range(2,upper+1):
     tp = Base_10_to_n(n, i)
     if tp == s: 
        #print(s,i)
        ans = min(ans,i)
     #print(ans)
  #√n以上を探す
  for p in range(0,upper+5):
    if (n-s)%(p+1) != 0:
      continue
    else:
      td = Base_10_to_n(n, (n-s)//(p+1))
      
      if td == s: 
        ans = min(ans,(n-s)//(p+1))
        #print(ans)
  
  if ans != 10**15:
   print(ans)
  else:
   print(-1)
solve()

Submission status: Wrong Answer

Solution code:
#http://arc060.contest.atcoder.jp/data/arc/060/editorial.pdf
def Base_10_to_n(X, n):
    if X < 2: return -1
    if n < X: return n
    return (n%X) + Base_10_to_n(X,n//X)

def solve():
  n = int(input())
  s = int(input())
  ans = 10**15
  if s == n :
    print(n+1)
    exit()
  elif n < s :
    print(-1)
    exit()
  else:
    upper = int(pow(n, 0.5))
    for i in range(2,upper+1):
     tp = Base_10_to_n(n, i)
     if tp == s: ans = min(ans,i)
  #√n以上を探す
  for p in range(0,upper+5):
    if (n-s)%(p+1) != 0:
      continue
    else:
      td = Base_10_to_n(n, (n-s)//(p+1))
      
      if td == s: 
        ans = min(ans,(n-s)//(p+1))
        #print(ans)
  td = Base_10_to_n(n, n)
  if td == s:
   ans = min(ans,n)
  
  if ans != 10**15:
   print(ans)
  else:
   print(-1)
solve()

Submission status: Wrong Answer

Solution code:
#http://arc060.contest.atcoder.jp/data/arc/060/editorial.pdf
def Base_10_to_n(X, n):
    X_dumy = X
    out = 0
    while X_dumy>0:
        out += X_dumy%n
        X_dumy = int(X_dumy/n)
    return out

def solve():
  n = int(input())
  s = int(input())
  if n < s:
    print(-1)
    exit()
  if s == n :
    print(n+1)
    exit()
  else:
    upper = int(pow(n, 0.5))
    ans = 10**15
    for i in range(2,upper+5):
     tp = Base_10_to_n(n, i)
     if tp == s: ans = min(ans,i)
  #√n以上を探す
  for p in range(0,upper+5):
    if (n-s)%(p+1) != 0:
      continue
    else:
      td = Base_10_to_n(n, (n-s)//(p+1))
      
      if td == s: 
        ans = min(ans,(n-s)//(p+1))
        print(ans)
  td = Base_10_to_n(n, n)
  if td == s:
   ans = min(ans,n)
  
  if ans != 10**15:
   print(ans)
  else:
   print(-1)
solve()

Submission status: Wrong Answer

Solution code:
import sys

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

    if b > n:
        return n

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


def main():
    input = sys.stdin.readline
    n = int(input())
    s = int(input())

    if s > n:
        return -1

    if s == n:
        return n+1

    for i in range(2, int(n**0.5)):
        if f(i, n) == s:
            return i

    for p in range(int(n**0.5), 0, -1):
        if (n - s) % p != 0:
            continue

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

    return -1


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

Submission status: Wrong Answer

Solution code:
import math


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


def digit_sum(n: int, s: int) -> int:
    if n == s:
        return n + 1

    sqrt = math.sqrt(n)
    sqrt = math.ceil(sqrt)

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

    for p in range(1, sqrt + 1):
        b = (n - s) // p + 1

        if b < 2:
            continue

        if f(b, n) == s:
            return b

    return -1


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

Submission status: Wrong Answer

Solution code:
import math


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


def digit_sum(n: int, s: int) -> int:
    if n == s:
        return n + 1

    sqrt = math.sqrt(n)
    sqrt = math.ceil(sqrt + 1)

    for b in range(2, sqrt):
        if f(b, n) == s:
            return b

    for p in range(1, sqrt):
        b = (n - s) // p + 1

        if b < 2:
            continue

        if f(b, n) == s:
            return b

    return -1


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

Submission status: Wrong Answer

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


def digit_sum(n: int, s: int) -> int:
    for b in range(2, n + 1):
        if f(b, n) == s:
            return b
    return -1


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

Submission status: Wrong Answer

Solution code:
import numpy as np
n=int(input())
s=int(input())
memo=[{} for i in range(n)]
def f(b,n):
  if n in memo[b]:
    return memo[b][n]
  if n<b:
     return n
  if n>=b:
     memo[b][n]=f(b,int(n/b))+n%b
     return memo[b][n]

def solve():
  if s==n:
    return n+1
  if s==1:
    return n
  for i in range(2,int(n**(0.5))):
    if s==f(i,n):
      return i 
  return -1
print(solve())

Submission status: Wrong Answer

Solution code:
from sys import stdin
import sys
sys.setrecursionlimit(10000)
input = stdin.readline

n = int(input().rstrip())
s = int(input().rstrip())

def f(b, n):
	if n < b:
		return n
	else:
		return f(b, int(n/b)) + (n % b)
if s == n:
	print(n+1)
else:
	for i in range(2, int(n**(1/2))+1):
		if f(i, n) == s:
			print(i)
			break
	else:
		for p in range(1, int(n**(1/2))+1):
			if (n-s) % p == 0:
				b = (n-s)/p + 1
				if b >= 2 and f(b, n) == s:
					print(int(b))
					break
			else:
				continue
		else:
			print(-1)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import sys
sys.setrecursionlimit(10000)
input = stdin.readline

n = int(input().rstrip())
s = int(input().rstrip())

def f(b, n):
	if n < b:
		return n
	else:
		return f(b, int(n/b)) + (n % b)
if s == n:
	print(n+1)
else:
	for i in range(2, int(n**(1/2))+1):
		if f(i, n) == s:
			print(i)
			break
	else:
		for p in range(1, int(n**(1/2))+1):
			b = (n-s)/p + 1
			if b >= 2 and f(b, n) == s:
				print(int(b))
				break
		else:
			print(-1)

Submission status: Wrong Answer

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

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

ans=-1
if s==n:
	ans=n+1
else:
	for _b in range(2,int(n**0.5)+1):
		if f(_b,n)==s:
			ans=_b
			break
	if ans==-1:
		for _p in range(int(n**0.5)+1,1,-1):
			_b = (n-s)//_p+1
			if f(_b,n)==s:
				ans=_b
				break
print(ans)

Submission status: Wrong Answer

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

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

ans=-1
if s==n:
	ans=n+1
else:
	for _b in range(2,int(n**0.5)+1):
		if f(_b,n)==s:
			ans=_b
			break
	for _p in range(1,int(n**0.5)+1):
		_b = (n-s)//_p+1
		if f(_b,n)==s:
			ans=_b
			break
print(ans)

Submission status: Wrong Answer

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

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

ans=-1
if s==n:
	ans=n+1
else:
	for _b in range(2,int(n**0.5)+1):
		if f(_b,n)==s:
			ans=_b
			break
	if ans==-1:
		for _p in range(1,int(n**0.5)+1):
			_b = (n-s)//_p+1
			if f(_b,n)==s:
				ans=_b
				break
print(ans)

Submission status: Wrong Answer

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

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

m = int(n ** 0.5) + 1

for b in range(2, m + 1):
    temp = n
    t = 0
    while temp >= b:
        t += temp % b
        temp //= b
    if s == t + temp:
        print(b)
        exit()

for p in range(1, m + 1):
    if (n - s) % p != 0:
        continue
    b = (n - s) // p + 1
    temp = n
    t = 0
    while temp >= b:
        t += temp % b
        temp //= b
    if s == t + temp:
        print(b)
        exit()

print(-1)

Submission status: Wrong Answer

Solution code:
#ABC044D
def fun(b,n):
    if n<b:return n
    return (n%b)+fun(b,n//b)
n=int(input())
s=int(input())
n_root=n**0.5

def main(n,n_root,s):
    if s==n:return n+1
    if s>n:return -1
    if s==1:return n
    if (n//2)+1<s:return -1
    for b in range(2,1+int(n_root)):
        if fun(b,n)==s:
            return b
    for i in range(int(n_root),0,-1):
        b=1+(n-s)//i
        if b<=1:continue
        if fun(b,n)==s:
            if b>1:return b
    return -1
print(main(n,n_root,s))

Submission status: Wrong Answer

Solution code:
#ABC044D
def fun(b,n):
    if n<b:return n
    return (n%b)+fun(b,n//b)
n=int(input())
s=int(input())
n_root=n**0.5

def main(n,n_root,s):
    if s==n:return n+1
    if s>n:return -1
    if s==1:return n
    for b in range(2,2+int(n_root//1)):
        if fun(b,n)==s:
            return b
    for i in range(1+int(n_root//1),0,-1):
        if (n-s)%i==0:
            b=(n-s+i)//i
            if b<=n_root:continue
            if n//b>=b or n//b<1:continue
            if n//b+n%b==s:
                return b
    return -1
print(main(n,n_root,s))

Submission status: Wrong Answer

Solution code:
#ABC044D
def fun(b,n):
    if n<b:return n
    return (n%b)+fun(b,n//b)
n=int(input())
s=int(input())
n_root=n**0.5

def main(n,n_root,s):
    if s==1:return n
    if s==n:return n+1
    if s>n:return -1
    for b in range(2,1+int(n_root//1)):
        if fun(b,n)==s:
            return b
    for i in range(int(n_root//1),0,-1):
        if (n-s)%i==0:
            b=(n-s+i)//i
            if b<=n_root:continue
            if n//b>=b or n//b<1:continue
            if n//b+n%b==s:
                return b
    return -1
print(main(n,n_root,s))

Submission status: Wrong Answer

Solution code:
#ABC044D
def fun(b,n):
    if n<b:return n
    return (n%b)+fun(b,n//b)
n=int(input())
s=int(input())
n_root=n**0.5

def main(n,n_root,s):
    if s==1:return n
    if s==n:return n+1
    if s>n:return -1
    for b in range(2,1+int(n_root//1)):
        if fun(b,n)==s:
            return b
    for i in range(int(n_root//1),0,-1):
        if (n-s)%i==0:
            b=(n-s+i)//i
            if b<n_root:continue
            if n//b+n%b==s:
                return b
    return -1
print(main(n,n_root,s))

Submission status: Wrong Answer

Solution code:
#ABC044D
def fun(b,n):
    if n<b:return n
    return (n%b)+fun(b,n//b)
n=int(input())
s=int(input())
n_root=1
while n_root**2<n:
    n_root+=1
def main(n,n_root,s):
    if s==1:return n
    if s==n:return n+1
    if s>n:return -1
    for b in range(2,n_root):
        if fun(b,n)==s:
            return b
    for i in range(n_root,0,-1):
        if (n-s)%i==0:
            b=(n-s+i)//i
            if b<n_root:continue
            if n//b+n%b==s:
                return b
    return -1
print(main(n,n_root,s))

Submission status: Wrong Answer

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

flag = False
if s > n or (n//2)<s<n:
  print(-1)
  exit()
  
if s == n:
  print(n+1)
  exit()

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

for b in range(2, int(n**0.5)+1):
  if chk(b, n) == s:
    print(b)
    flag = True
    exit()

for i in range(int(n**0.5), 0, -1):
  b = (n-s)//i + 1
  if chk(b, n) == s:
    if b > 1:
      print(b)
      flag = True
      exit()

if flag == False:
  print(-1)

Submission status: Wrong Answer

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

flag = False
if s > n:
  print(-1)
  exit()
if s > n/2:
  print(-1)
  exit()
  
if s == n:
  print(n+1)
  exit()

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

for b in range(2, int(n**0.5)+1):
  if chk(b, n) == s:
    print(b)
    flag = True
    exit()

for i in range(int(n**0.5), 0, -1):
  b = (n-s)//i + 1
  if chk(b, n) == s:
    print(b)
    flag = True
    exit()

if flag == False:
  print(-1)

Submission status: Wrong Answer

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

flag = False

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

import math
def chk(b, n):
  if b//n == 0:
    return n
  else:
    return chk(b,math.floor(n/b))+n%b

for b in range(2, int(n**0.5)+1):
  if chk(b, n) == s:
    print(chk(b,n))
    print(b)
    flag = True
    break

for i in range(int(n**0.5), n, -1):
  b = (n-s)/i + 1
  if chk(b, n) == s:
    print(b)
    flag = True
    break

if flag == False:
  print(-1)

Submission status: Wrong Answer

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

"""
・参考：http://arc060.contest.atcoder.jp/data/arc/060/editorial.pdf
　　　　https://www.youtube.com/watch?v=LzxPxJ-cSHk
・b <= √nは愚直に当たっていく。
・b > √nは、b^2 > nなので、b進数で2桁以下になる。
　例) 10^2は10進数で100、100 > n → nは99以下
　その2桁の数字はn = p*b + qと表せる。
　例) 67 = 6*10 + 7
　今回の問題の条件から、s = p + q
　n = p*b + q
　s = p + q
　上記2つの式から、連立方程式でqを消すと、
　n-s = p*b - p
　と表せる。
　pはb以上なら桁が上がってしまうので p < b
　p < b から p*p < p*b なので、p*b > p^2
　よって、n = p*b + q >= p*b > p^2
　n > p^2 なので、√n > p
　つまりpについて√nまでを全探索すればOK。
　n-s = p*b - p をbについての形に変形すればbが出せる。
　b = (n-s)/p + 1
"""

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

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

n = INT()
s = INT()

if s > n:
    print(-1)
elif s == n:
    print(n+1)
elif ceil(n/2) < s < n:
    print(-1)
else:
    # b <= √n の全探索
    for b in range(2, int(sqrt(n))+2):
        if f(b, n) == s:
            print(b)
            exit()
    # b > √n について、式を元に探す
    for p in range(1, int(sqrt(n))+2):
        # 整数にならないものは除外
        if (n-s)%p: continue
        b = (n-s)//p + 1
        if f(b, n) == s:
            print(b)
            exit()
    # 見つからなかった
    print(-1)

Submission status: Wrong Answer

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

"""
・参考：http://arc060.contest.atcoder.jp/data/arc/060/editorial.pdf
　　　　https://www.youtube.com/watch?v=LzxPxJ-cSHk
・b <= √nは愚直に当たっていく。
・b > √nは、b^2 > nなので、b進数で2桁以下になる。
　例) 10^2は10進数で100、100 > n → nは99以下
　その2桁の数字はn = p*b + qと表せる。
　例) 67 = 6*10 + 7
　今回の問題の条件から、s = p + q
　n = p*b + q
　s = p + q
　上記2つの式から、連立方程式でqを消すと、
　n-s = p*b - p
　と表せる。
　pはb以上なら桁が上がってしまうので p < b
　p < b から p*p < p*b なので、p*b > p^2
　よって、n = p*b + q >= p*b > p^2
　n > p^2 なので、√n > p
　つまりpについて√nまでを全探索すればOK。
　n-s = p*b - p をbについての形に変形すればbが出せる。
　b = (n-s)/p + 1
"""

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

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

n = INT()
s = INT()

if s > n:
    print(-1)
elif s == n:
    print(n+1)
elif ceil(n/2) < s < n:
    print(-1)
else:
    # b <= √n の全探索
    for i in range(2, int(sqrt(n))+2):
        if f(i, n) == s:
            print(i)
            exit()
    # b > √n について、式を元に探す
    for p in range(1, int(sqrt(n))+2):
        b = (n-s)/p + 1
        if f(b, n) == s:
            print(int(b))
            exit()
    # 見つからなかった
    print(-1)

Submission status: Wrong Answer

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

"""
・参考：http://arc060.contest.atcoder.jp/data/arc/060/editorial.pdf
　　　　https://www.youtube.com/watch?v=LzxPxJ-cSHk
・b <= √nは愚直に当たっていく。
・b > √nは、b^2 > nなので、b進数で2桁以下になる。
　例) 10^2は10進数で100、100 > n → nは99以下
　その2桁の数字はn = p*b + qと表せる。
　例) 67 = 6*10 + 7
　今回の問題の条件から、s = p + q
　n = p*b + q
　s = p + q
　上記2つの式から、連立方程式でqを消すと、
　n-s = p*b - p
　と表せる。
　pはb以上なら桁が上がってしまうので p < b
　p < b から p*p < p*b なので、p*b > p^2
　よって、n = p*b + q >= p*b > p^2
　n > p^2 なので、√n > p
　つまりpについて√nまでを全探索すればOK。
　n-s = p*b - p をbについての形に変形すればbが出せる。
　b = (n-s)/p + 1
"""

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

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

n = INT()
s = INT()

if s > n:
    print(-1)
elif s == n:
    print(n+1)
elif ceil(n/2) < s < n:
    print(-1)
else:
    # b <= √n の全探索
    for i in range(2, int(sqrt(n))+2):
        if f(i, n) == s:
            print(i)
            exit()
    # b > √n について、式を元に探す
    for p in range(1, int(sqrt(n))+2):
        b = (n-s)/p + 1
        if f(b, n) == s:
            print(int(b))
            exit()

Submission status: Wrong Answer

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

def fun(b,n):
    if n<b:return n
    elif n>=b:
        return fun(b,n//b)+n%b
def main(n,s):
    b=2
    while b<=n:
        if fun(b,n)==s:return b
        b+=1
    return -1

if s==n:print(n+1)
elif s==1:print(n)
else:
    x=main(n,s)
    print(x)

Submission status: Wrong Answer

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
limN = int(N**.5)+1
for b in range(2,limN):
    if f(b,N)==S:
        ans = b
        break

print(ans)

Submission status: Wrong Answer

Solution code:
import math
import sys

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

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


for i in range(2,int(math.sqrt(n))+5):
    if digsum(i,n)==s:
        print(i)
        sys.exit()

for i in range(int(math.sqrt(n)),0,-1):

    if s-i>=0 and n-(s-i)>=0 and (n-(s-i))%i==0 and (n-(s-i))//i>s-i:
        print((n-(s-i))//i)
        sys.exit()

print(-1)

Submission status: Wrong Answer

Solution code:
import math

def gcd(a,b):
    """Compute the greatest common divisor of a and b"""
    while b > 0:
        a, b = b, a % b
    return a
 
def lcm(a, b):
    """Compute the lowest common multiple of a and b"""
    return a * b / gcd(a, b)
 

def f(b,n):
	if n < b:
		return n
	return f(b, n//b) + n%b
 
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(math.sqrt(N))+1):
	if(f(B,N)==S):
		print(B)
		exit()


for p in range(int(math.sqrt(N))+1, 0, -1):
	B = (N-S)/p + 1
	if(B==int(B) and f(int(B),N)==S):
		print(B)
		exit()


print(-1)

Submission status: Wrong Answer

Solution code:
import math

def gcd(a,b):
    """Compute the greatest common divisor of a and b"""
    while b > 0:
        a, b = b, a % b
    return a
 
def lcm(a, b):
    """Compute the lowest common multiple of a and b"""
    return a * b / gcd(a, b)
 

def f(b,n):
	if n < b:
		return n
	return f(b, n//b) + n%b
 
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(math.sqrt(N))+1):
	if(f(B,N)==S):
		print(B)
		exit()


for p in range(int(math.sqrt(N)),0,-1):
	B = (N-S)/p + 1
	if(B==int(B) and f(int(B),N)==S):
		print(B)
		exit()


print(-1)

Submission status: Wrong Answer

Solution code:
import math,sys


sys.setrecursionlimit(1500)


def gcd(a,b):
    """Compute the greatest common divisor of a and b"""
    while b > 0:
        a, b = b, a % b
    return a
 
def lcm(a, b):
    """Compute the lowest common multiple of a and b"""
    return a * b / gcd(a, b)
 

def f(b,n):
	if n < b:
		return n
	return f(b, n//b) + n%b
 
N = int(input())
S = int(input())

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

if N < S:
	print(-1)
	exit()

for B in range(2, int(math.sqrt(N))+1):
	if(f(B,N)==S):
		print(B)
		exit()


for p in range(int(math.sqrt(N)),0,-1):
	B = (N-S)/p + 1
	if(B==int(B) and f(int(B),N)):
		print(B)
		exit()


print(-1)