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):
    if n < b: return n
    return f(b, n//b) + n%b

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

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

# "pq"(b)
# b*p + q = N
# p + q = S
# (b-1)p = N-S

while b <= N:
    if (N-S)%(b-1)==0 and f(b,N) == S:
        print(b)
        exit()
    b += 1
print(-1)

Submission status: Wrong Answer

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
    su = b
    while su > 0:
        if n%su == s-su:
            print(n//su)
            return
        su-=1
    if n == s:
        print(s+1)
        return
    print(-1)
    return



if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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
    su = n // b
    while su > 0:
        if n%su == s-su:
            print(n//su)
            return
        su-=1
    print(-1)
    return



if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
m=int(input())

s=int(input())

def fromten(a,y):

    b=0

    while a!=0:

        b+=a%y

        a=a//y

    return b

 

f=True

for i in range(2,int(m**0.5)+1):

    if fromten(m,i)==s:

        print(i)

        f=False

        break

if f:

    z=m-s

    flag=False

    for a in range(int(m**0.5),0,-1):###  z+1 

        if z%a==0:

            q=z//a+1

            b=m-a*q

            q=z//a+1

            if a+b==s and a*q+b==m:

                print(q)

                flag=True

                break

    if not flag:

        if m%s==0:

            print(m//s)

        else:

            print(-1)

Submission status: Wrong Answer

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

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:
    sqrt_n = int(n ** 0.5)
    for b in range(2, sqrt_n + 1):
        if f(b, n) == s:
            ans = b
            break
    else:
        for p in range(1, sqrt_n):
            if (n - s) % p != 0:
                continue
            b = (n - s) // p + 1
            if sqrt_n < b <= n and f(b, n) == s:
                ans = b
print(ans)

Submission status: Wrong Answer

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

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:
    sqrt_n = int(n ** 0.5)
    for b in range(2, sqrt_n + 1):
        if f(b, n) == s:
            ans = b
            break
    else:
        for p in range(1, sqrt_n):
            if (n - s) % p != 0:
                continue
            b = (n - s) // p + 1
            if sqrt_n < b <= n and f(b, n) == s:
                ans = b
                break
print(ans)

Submission status: Wrong Answer

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

if n < s:
    print -1
elif s == 1:
    print n
else:
    ans_list = []
    for i in xrange(n/2, 1, -1):
        tmp_n = n
        total = 0
        while tmp_n / i > 0:
            total += tmp_n % i
            tmp_n /= i
        total += tmp_n

        print i, total
        if total == s:
            ans_list.append(i)

    print ans_list[len(ans_list)-1] if ans_list else -1

Submission status: Wrong Answer

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
    ns = n - s * 1.0
    for i in range(sq+1,1,-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: Wrong Answer

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(1,sq+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: Wrong Answer

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
    if n % s == 0 and n//s > s:
        return n//s
    sq = int(math.sqrt(n))
    for i in range(2,sq+1):
        if g(n, i) == s:
            return i
    ns = n - s * 1.0
    for i in range(1,sq+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: Wrong Answer

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
    ns = n - s * 1.0
    for i in range(1,sq+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: Wrong Answer

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
    ns = n - s * 1.0
    for i in range(1,sq+1):
        b = ns / i + 1
        if b != int(b):
            continue
        if g(n, b) == s:
            return b
    return -1

print(f())

Submission status: Wrong Answer

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
    for i in range(1,sq+1):
        b = s - i + 1
        if g(n, b) == s:
            return b
    return -1

print(f())

Submission status: Wrong Answer

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
    ns = n - s
    for i in range(1,sq+1):
        b = ns // i + 1
        if g(n, b) == s:
            return b
    return -1

print(f())

Submission status: Wrong Answer

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)
    for i in div:
        if i>=10**6:
            if f(i+1,n)==s:
                print(i+1)
                quit()
    print(-1)

Submission status: Wrong Answer

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

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<=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)
    for i in div:
        if i>=10**6:
            if f(i+1,n)==s:
                print(i+1)
                quit()
    print(-1)

Submission status: Wrong Answer

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

N = int(input())
S = int(input())
flag = 0
for i in range(2,N):
    if calc(i,N)==S:
        flag = 1
        print(i)
        break

if flag==0:
    print("-1")

Submission status: Wrong Answer

Solution code:
import math

ans = -1

def f(b, n):

  l = []

  for i in range(n):
    l.append(n % b)
    n /= b

  return sum(l)

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

for b in range(2, n + 1):

  if n == s:
    ans = 1
    break

  elif s > n:
    break

  elif f(b, n) > n:
    break

  elif f(b, n) == s:
    ans = b
    break

print ans

Submission status: Time Limit Exceeded

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, max(n + 1, MAX) + 1):
        sm = digit_sum(n, b)
        if sm == s:
            ans = b
            break

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

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

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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, max(n + 1, MAX) + 1):
        sm = digit_sum(n, b)
        if sm == s:
            ans = b
            break

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

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

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

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = int(input())
x = int(n**0.5)+1
def dsum(x,t):
  ret = 0
  while x>0:
    ret += x%t
    x //= t
  return ret
for i in range(1,x+1):
  if dsum(n,i) == s:
    print(i)
    exit()
for i in range(x,0,-1):
  if n//i+n%i == t:
    print(n//i)
    exit()

Submission status: Time Limit Exceeded

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

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

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

def func(b, N):
    if b == 0:
        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):
        num = (N-S+x)//x
        b = num//x
        if func(b, N) == S:
            print(b)
            break
    else:
        print(-1)

Submission status: Time Limit Exceeded

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

def ok(x):
  ret=0
  n_=n
  while n_>0:
    ret+=n_%x
    n_//=x
  if s == ret:
    return True
  return False

g = abs(n-s)
from math import sqrt,floor
for x in range(1,floor(sqrt(g)+10)):
  if g%x ==0 and ok(x+1):
    print(x+1)
    exit()
      
rev = list(range(1,floor(sqrt(g)+10)))
rev.reverse()
for x in rev:
  if g%x == 0 and ok(g//x+1):
    print(g//x+1)
    exit()
      
print(-1)

Submission status: Time Limit Exceeded

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()