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:
from math import sqrt
import sys
sys.setrecursionlimit(10**6)
def f(b, n):
	if n < b:
		return n
	else:
		return f(b, n // b) + n % b

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

if n < s:
	print(-1)
elif n == s:
	print(n+1)
else:
	divs = []
	for i in range(1, int(sqrt(n-s))+1):
		if (n-s)%i == 0:
			divs.append(i)
			if i != (n-s)//i:
				divs.append((n-s)//i)
	divs.sort()
	for d in divs:
		if f(d+1, n) == s:
			print(d+1)
			break
	else:
		print(-1)

Submission status: Accepted

Solution code:
from math import floor
from math import sqrt

def f(bb,nn):
    if(nn<bb): return nn
    else: return f(bb,floor(nn/bb))+(nn%bb)
        

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

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

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

for i in reversed(range(1,int(sqrt(n))+2)):
    if (n-s)%i == 0:
        tmpb=(n-s)//i+1
        if tmpb >= sqrt(n) and f(tmpb,n)==s: 
            print(tmpb)
            exit()
print(-1)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from math import floor, sqrt

def digit_sum(num:int, base:int) -> int:

    if num < base:
        return num
    else:
        return digit_sum(int(num/base), base) + (num % base)
    
n = ni()
s = ni()

root = floor(sqrt(n))
ans = float("inf")

# 3桁以上
for p in range(2, root+1):
    ds = digit_sum(n,p)
    if ds == s:
        ans = min(ans, p)
        

# 2桁
for a in range(1,root+2):
    p = (n-s+a) / a
    b = s - a
    if p == int(p) and 0 < a < p and 0 <= b < p:
        ans = min(ans, int(p))

# 1桁
if n == s:
    ans = min(ans, n+1)
    
print(-1) if ans == float("inf") else print(ans)

Submission status: Accepted

Solution code:
from math import sqrt

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

#nをb進法表記したときの桁和
def f(b, n):
    res = 0
    while n:
        res += n % b
        n //= b
    return res
    
# s = n
if s == n:
    print(n+1)
    exit()

 
# 2 <= b <= sqrt(n)
for b in range(2, int(sqrt(n))+1):
    if f(b, n) == s:
        print(b)
        exit()
 
# 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 b*b <= n:
        continue
    if f(b, n) == s:
        print(b)
        exit()
print(-1)

Submission status: Accepted

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

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

if S > N:
    print(-1)
elif S == N:
    print(N + 1)
else:
    sqrt = int(pow(N, 0.5))
    for b in range(2, sqrt + 1):
        if sum_digit(b, N) == S:
            print(b)
            quit()
    for k in reversed(range(1, sqrt + 1)):
        if (N - S) % k == 0:
            b = (N - S) // k + 1
            if sum_digit(b, N) == S:
                print(b)
                quit()
    print(-1)

Submission status: Accepted

Solution code:
n=int(input())
s=int(input())
ans=-1
def f(a,x):
  if a>x:
    return x
  else:
    return f(a,x//a)+(x%a)
  
for i in range(2,int(n**(1/2))+1):
  if ans<0 and f(i,n)==s:
    ans=i
  

for p in range(1,int(n**(1/2))+1)[::-1]:
  if ans<0:
    if s-p>=0 and (n+p-s)%p==0:
      b=(n+p-s)//p
      if b>=p+1 and b>=s-p+1:
        ans=b
    
if ans<0 and n==s:
  ans=(n+1)

print(ans)

Submission status: Accepted

Solution code:
import math
import sys
n=int(input())
s=int(input())
l=n-s
def f(b):
    t=0
    u=n
    while u!=0:
        t+=u%b
        u=u//b
    return t
N=math.ceil(math.sqrt(n)+2)
T=10**12
if l<0:
    print(-1)
    sys.exit()
if l==0:
    print(n+1)
    sys.exit()
for i in range(1,N):
    if l%i==0:
        j=i+1
        if f(j)==s and T>j:
            T=j
        elif f((l//i)+1)==s and T>((l//j)+1):
            T=(l//i)+1
if T==10**12:
    print(-1)
    sys.exit()
print(T)

Submission status: Accepted

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)


def abc(N,S):
    if N==S:
        return N+1
    else:
        for b in range(2,int(math.sqrt(N))+2):
            if f(b,N)==S:
                return b
        tmp=-1
        for p in range(1,int(math.sqrt(N))+2):
            if (N-S)%p!=0:
                continue
            b=(N-S)//p+1
            if b<=1:
                continue
            if f(b,N)==S:
                tmp=b
        return tmp
ans=abc(n,s)
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)
N=int(input())
S=int(input())
if N==S:
    print(N+1)
else:
    for b in range(2,int(math.sqrt(N))+2):
        if f(b,N)==S:
            print(b)
            exit()
    ans=10**13
    for p in range(1,int(math.sqrt(N))+2):
        if (N-S)%p!=0:
            continue
        b=(N-S)//p+1
        if b<=1:
            continue
        if f(b,N)==S:
            ans=b
    if ans==10**13:
        print(-1)
    else:
        print(ans)

Submission status: Accepted

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

n = int(input())
s = int(input())
inf = float('inf')
ans = inf

for i in range(2,int(n**(1/2))+2):
    if digitsum(n,i) == s:
        ans = i
        break
if n == s:
    ans = n+1
else:
    for i in range(1,int(n**(1/2))):
        if i*i-i >= n-s:
            break
        if (n-s) % i == 0:
            if s-i >= (n-s)//i +1 or i > s:
                continue
            ans = min(ans,((n-s)//i)+1)
            
if ans == inf:
    print(-1)
else:
    print(int(ans))

Submission status: Accepted

Solution code:
from math import floor, sqrt

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

def solve(n, s):
    if s > n:
        return -1
    elif s == n:
        return n + 1

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

    for p in reversed(range(1, floor(sqrt(n)) + 1)):
        if (n - s) % p == 0:
            b = (n - s) // p + 1
            q = n - p * b
            if 1 <= p < b and 0 <= q < b:
                return b

    return -1


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

print(solve(n, s))

Submission status: Accepted

Solution code:
from math import floor, sqrt

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

def solve(n, s):
    if s > n:
        return -1
    elif s == n:
        return n + 1

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

    for p in reversed(range(1, floor(sqrt(n)) + 1)):
        if (n - s) % p == 0:
            b = (n - s) // p + 1
            if f(b, n) == s:
                return b

    return -1


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

print(solve(n, s))

Submission status: Accepted

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

    b = 2
    while b**2 < n:
        if f(b, n) == s:
            return b

        b += 1

    p = int(n ** 0.5)
    while p >= 1:
        b = (n - s) // p + 1
        if b > 1 and f(b, n) == s:
            return b
        
        p -= 1

    return -1


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

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

def solve():
    n = int(input())
    s = int(input())
    result = digit_sum(n, s)
    print(result)

solve()

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def digit_sum(num:int, base:int) -> int:

    if num < base:
        return num
    else:
        return digit_sum(int(num/base), base) + (num % base)

n = ni()
s = ni()

ans = -1

if s > n:
    ans = -1
  
elif s == n:
    ans = n+1
    
else:
    base = 2
    exist = False
    while base*base <= n:
        ds = digit_sum(n,base)
        if ds == s:
            ans = base
            exist = True
            break
        
        base += 1
        
    
    if not exist:
        for p in range(base,0,-1):
            if (n-s+p)%p == 0 and s-p >= 0:
                b = (n-s+p)//p
                if b > p and b > s-p:
                    ans = b
                    exist = True
                    break
            
print(ans)

Submission status: Accepted

Solution code:
n, s = [int(input()) for _ in range(2)]
def f(b, n):
    if n < b:
        return n
    return f(b, n // b) + n % b

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

for i in range(2, int(n ** .5) + 1):
    if s == f(i, n):
        print(i)
        exit()

for i in reversed(range(1, int(n ** .5) + 1)):
    b = (n - s) // i + 1
    if b > 1 and s == f(b, n):
        print(b)
        exit()
print(-1)

Submission status: Accepted

Solution code:
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()
for b in range(2,int(n**0.5)+1):
  if f(b,n)==s:
    print(b)
    break
else:
  for p in range(1,int(n**0.5)+1)[::-1]:
    b,m=divmod(n-s+p,p)
    if m==0 and b>=2 and f(b,n)==s:
      print(b)
      break
  else:
    print(-1)

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 build_div(x):
    i = 1
    ret = []
    if x < 0:
        return ret
    while True:
        if i*i > x:
            break
        if x % i == 0:
            ret.append(i)
            ret.append(x//i)
        i += 1
    return sorted(ret)


n = int(input())
s = int(input())
b = -1
if n == s:
    print(n+1)
else:
    for i in range(2, math.ceil(math.sqrt(n))):
        if f(i, n) == s:
            b = i
            print(b)
            break
    if b == -1:
        div = build_div(n-s)
        for i in div:
            if f(i+1, n) == s:
                b = i+1
                print(b)
                break
    if b == -1:
        print(-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(10000000)

n = input()
s = input()

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

if n < s:
    print -1
    exit()

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

ans = -1
for p in range(1, 10 ** 6):
    if (n - s) % p == 0:
        i = (n - s) / p + 1
        q = s - p
        if p < i and 0 <= q < i:
            ans = (n - s) / p + 1

print ans

Submission status: Accepted

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

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

    for b in range(2, int(n**0.5)+1):
        x, sb = n, 0
        while 0 < x:
            sb += x % b
            x //= b
        if sb == s:
            print(b)
            return

    for p in range(1, int(n**0.5)+1)[::-1]:
        if (n-s) % p:
            continue
        b, x, sb = (n-s) // p + 1, n, 0
        while 0 < x:
            sb += x % b
            x //= b
        if sb == s:
            print(b)
            return

    print(-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections

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

def solve():
    n = int(input())
    s = int(input())
    b = int(2)
    while b*b <= n:
        if f(n,b) == s:
            print(b)
            return
        b+=1
    b = 0
    a = int(1)
    while a*a <= n-s:
        if (n-s)%a == 0 and\
        (n-s)//a >= a and\
        (s-a) >= 0 and\
        (n-s)//a >= (s-a):
            b = (n-s)//a+1
            # print(b,s-a)
        a+=1
    if b > 0:
        print(b)
        return
    if n == s:
        print(n+1)
        return
    print(-1)
    return



if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from math import sqrt


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


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

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

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

for p in reversed(range(1, int(sqrt(n)+1))):
    if (n - s) % p == 0:
        b = int((n - s) / p + 1)
        if f(b, n) == s:
            print(b)
            quit()

print(-1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from math import sqrt
n = int(input())
s = int(input())

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

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

for b in range(2, int(sqrt(n))+1):
    if f(b, n) == s:
        print(b)
        break
else:
    for p in range(1, int(sqrt(n))+1)[::-1]:
        d, m = divmod(p+n-s, p)
        if m == 0 and d >= 2 and f(d, n) == s:
            print(d)
            break
    else:
        print(-1)

Submission status: Accepted

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

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

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

ans = -1
if n == s:
    ans = n + 1
else:
    for b in range(2, math.floor(n ** 0.5) + 1):
        if f(b, n) == s:
            ans = b
            break
    else:
        for p in range(1, math.ceil(n ** 0.5)):
            if (n - s) % p != 0:
                continue
            b = (n - s) // p + 1
            if math.floor(n ** 0.5) < b <= n and f(b, n) == s:
                ans = b
print(ans)

Submission status: Accepted

Solution code:
# coding :utf-8
import math

num_N = int(input())
num_S = int(input())


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


def solve():
    if num_S == num_N:
        return num_N + 1

    num_sqr = int(math.sqrt(num_N))
    for i in range(2, num_sqr + 1):
        if get_s(num_N, i) == num_S:
            return i

    if num_N % num_S == 0 and num_N // num_S > num_S:
        return num_N // num_S

    num_dif = num_N - num_S
    for i in range(num_sqr + 1, 0, -1):
        b = num_dif / i + 1
        if b != int(b) or b < 2:
            continue
        b = int(b)
        if get_s(num_N, b) == num_S:
            return b
    return -1


print(solve())

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7

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

def f():
    n = int(input())
    s = int(input())
    if s == n:
        return n + 1
    sq = int(math.sqrt(n))
    for i in range(2,sq+1):
        if g(n, i) == s:
            return i
    if n % s == 0 and n//s > s:
        return n//s
    ns = n - s * 1.0
    for i in range(sq+1,0,-1):
        b = ns / i + 1
        if b != int(b) or b < 2:
            continue
        b = int(b)
        if g(n, b) == s:
            return b
    return -1

print(f())

Submission status: Accepted

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

def divisor(x):
    div=[]
    for i in xrange(1,int(x**0.5)+1):
        if x%i==0:
            div.append(i)
            if i!=x/i:
                div.append(x/i)
    return div

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

n=int(raw_input())
s=int(raw_input())

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

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

for i in xrange(2,int(n**0.5)+1):
    if f(i,n)==s:
        print(i)
        quit()

div=divisor(n-s)
div.sort()
for i in div:
    if f(i+1,n)==s:
        print(i+1)
        quit()
print(-1)

Submission status: Accepted

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

def divisor(x):
    div=[]
    for i in xrange(1,int(x**0.5)+1):
        if x%i==0:
            div.append(i)
            if i!=x/i:
                div.append(x/i)
    return div

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

n=int(raw_input())
s=int(raw_input())

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

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

if n<=10**6:
    for i in xrange(2,n+2):
        if f(i,n)==s:
            print(i)
            quit()
    print(-1)
else:
    for i in xrange(2,10**6+1):
        if f(i,n)==s:
            print(i)
            quit()

    div=divisor(n-s)
    div.sort()
    for i in div:
        if i>=10**6:
            if f(i+1,n)==s:
                print(i+1)
                quit()
    print(-1)

Submission status: Accepted

Solution code:
from sys import exit
from itertools import product

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

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

def primes(n):
    numbers = set(range(n, 1, -1))
    primes = []
    while numbers:
        p = numbers.pop()
        primes.append(p)
        numbers.difference_update(set(range(p*2, n+1, p)))
    return sorted(primes)

PRIMES = primes(10**6)

def pfact(x):
  res = dict()
  while x > 1:
    for p in PRIMES:
      if p >= x**0.5 + 1:
        res[x] = res.get(x, 0) + 1
        x = 1
        break
      if x % p == 0:
        res[p] = res.get(p, 0) + 1
        x //= p
        break
  return res

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

def divisors(n):
  P = list(pfact(n).items())
  res = []
  for ds in product(*[range(e+1) for (p, e) in P]):
    res.append(prod(P[i][0]**ds[i] for i in range(len(P))))
  return sorted(res)

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

n = read()
s = read()

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

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

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

print(-1)