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:
import math
import sys
n=int(input())
s=int(input())
root=int(math.sqrt(n))

buf=10**12
if s==n:
    print(n+1)
    sys.exit()
for i in range(1,root+1):
    res=s-i
    x=(n-res)//i
    if x*i+res==n and x>1 and x>res:
        #print(x,i,res,s,n)
        buf=min(buf,x)
    pass
for i in range(2,root+2):
    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: Wrong Answer

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

buf=10**12
if s==n:
    print(n+1)
    sys.exit()
for i in range(1,root+1):
    res=s-i
    x=(n-res)//i
    if x*i+res==n and x>0 and x>res:
        #print(x,i,res,s,n)
        buf=min(buf,x)
    pass
for i in range(2,root+2):
    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: Wrong Answer

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

buf=10**12
if s==n:
    print(n+1)
    sys.exit()
for i in range(1,root+1):
    res=s-i
    x=(n-res)//i
    if x*i+res==n and x>0 and x>res:
        #print(x,i,res,s,n)
        buf=min(buf,x)
    pass
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: Wrong Answer

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

buf=10**11
if s==n:
    print(n+1)
    sys.exit()
for i in range(1,root+1):
    res=s-i
    x=(n-res)//i
    if x*i+res==n and x>0 and x>res:
        #print(x,i,res,s,n)
        buf=min(buf,x)
    pass
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**11 else -1)

Submission status: Wrong Answer

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

buf=10**11
if s==n:
    print(n+1)
    sys.exit()
for i in range(1,root+1):
    res=s-i
    x=(n-res)//i
    if x*i+res==n:
        buf=min(buf,x)
    pass

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)

Submission status: Wrong Answer

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

buf=10**11
if s==n:
    print(n+1)
    sys.exit()
if s>=n-root+1:
    print(-1)
    sys.exit()

if root<s<=n-root-1:
    buf=n-s+1
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)

Submission status: Wrong Answer

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

buf=10**11
if s==n:
    print(n+1)
    sys.exit()
if s>=n-root:
    print(-1)
    sys.exit()
if s>=root*2:
    print(n-s+1)
    sys.exit()

if s<=n-root-1:
    buf=n-s+1
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)

Submission status: Wrong Answer

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)
    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: Wrong Answer

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)
    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:
            S0 = search(p)
            if S == S0:
                ans = p
                break

        print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

if L < 0:
    print(-1)
elif L == 0:
    print(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:
        S0 = search(p)
        if S == S0:
            ans = p
            break

    print(ans)

Submission status: Wrong Answer

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

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

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

    print(ans)

Submission status: Wrong Answer

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

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

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

    print(ans)

Submission status: Wrong Answer

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

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

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

if S == 1:
    print(N)
    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: Wrong Answer

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

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

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

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

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

ans = float('inf')

for b in range(2, int(N**0.5) + 10):
    if 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: Wrong Answer

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(math.floor(n**0.5), 0, -1):
        r = s-p
        if r<0:
            continue
        if (n-r)%p == 0:
            b = (n-r)//p
            if r<b:
                return b
    return -1
print(solve(n, s))

Submission status: Wrong Answer

Solution code:
n=int(input())
s=int(input())
r=int(n**0.5)
for b in range(2,r+1):
	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: Wrong Answer

Solution code:
n=int(input())
s=int(input())
r=int(n**0.5)
for b in range(2,r+1):
	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
	if 0<=q<r and n>=s and(n-s)%p==0:
		b=1+(n-s)//p
		if r<=b:
			print(b)
			exit()
if n==s:
	print(n+1)
	exit()
print(-1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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]:
    print(p)
    b = (n-s)//p + 1
    if b > 1 and dsum(n, b) == s:
        print(b)
        exit()
print(-1)

Submission status: Wrong Answer

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

sqrt = 0
for i in range(n):
    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
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: Wrong Answer

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

sqrt = 0
for i in range(n):
    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-1
for b in range(2, sqrt):
    use_n = n
    ans_tmp = dsum(n, b)
    if ans_tmp == s:
        print(b)
        exit()

# n = p*b + q
# s = p + q
ans = []
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: Wrong Answer

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

sqrt = 0
for i in range(n):
    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-1
for b in range(2, sqrt):
    use_n = n
    ans_tmp = dsum(n, b)
    if ans_tmp == s:
        print(b)
        exit()

# n = p*b + q
# s = p + q
ans = []
for p in range(1, sqrt)[::-1]:
    b = (n-s)//p + 1
    if dsum(n, b) == s:
        print(b)
        exit()
print(-1)

Submission status: Wrong Answer

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

ans = []
if s == n:
    print(n+1)
    exit()
for i in range(2, n+1):
    use_n = n
    tmp_ans = 0
    if i*i > n:
        break
    while use_n:
        tmp_ans += use_n%i
        use_n //= i
    if tmp_ans == s:
        print(i)
        exit()
    
for p in range(1,n):
    if p*p > n or p >= 100:
        break
    q = s - p
    if q < 0 or 100 <= q:
        continue
    b = (n-q)//p
    if n == p*b + q and b*b > n:
        ans.append(b)

if len(ans):
    print(min(ans))
else:
    print(-1)

Submission status: Wrong Answer

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

ans = []
for i in range(2, n+1):
    use_n = n
    tmp_ans = 0
    if i*i > n:
        break
    while use_n:
        tmp_ans += use_n%i
        use_n //= i
    if tmp_ans == s:
        print(i)
        exit()
    
for p in range(1,n):
    if p*p > n or p >= 100:
        break
    q = s - p
    if q < 0 or 100 <= q:
        continue
    b = (n-q)//p
    if n == p*b + q and b*b > n:
        ans.append(b)
if len(ans):
    print(min(ans))
else:
    print(-1)

Submission status: Wrong Answer

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

ans = []
for i in range(2, n):
    use_n = n
    tmp_ans = 0
    if i*i > n:
        break
    while use_n:
        tmp_ans += use_n%i
        use_n //= i
    if tmp_ans == s:
        print(i)
        exit()
    
for p in range(2, n):
    if p*p > n or p >= 100:
        break
    q = s - p
    if not 0<=q<100:
        continue
    b = (n-q)//p
    if n == p*b + q and b*b > n:
        ans.append(b)
if len(ans):
    print(min(ans))
else:
    print(-1)

Submission status: Wrong Answer

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

ans = []
for i in range(2, n):
    use_n = n
    tmp_ans = 0
    if i*i > n:
        break
    while use_n:
        tmp_ans += use_n%i
        use_n //= i
    if tmp_ans == s:
        print(i)
        exit()
    
for p in range(2, n):
    if p*p > n or p >= 100:
        break
    q = s - p
    if not 0<=q<100:
        continue
    b = (n-q)//p
    if n == p*b + q:
        ans.append(b)
if len(ans):
    print(min(ans))
else:
    print(-1)

Submission status: Wrong Answer

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

ans = []
for i in range(2, n):
    use_n = n
    tmp_ans = 0
    if i*i > n:
        break
    while use_n:
        tmp_ans += use_n%i
        use_n //= i
    if tmp_ans == s:
        print("a")
        print(i)
        exit()
    
for p in range(2, n):
    if p*p > n or p >= 100:
        break
    q = s - p
    if not 0<=q<100:
        continue
    b = (n-q)//p
    if n == p*b + q:
        ans.append(b)
if len(ans):
    print(min(ans))
else:
    print(-1)

Submission status: Wrong Answer

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

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

for b in range(2, 100000000000):
    if(f(b,n)==s):
        print(b)
        break
    if(b>n and b!=s):
        print(-1)
        break
else:
    print(-1)

Submission status: Wrong Answer

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

n = int(input())
s = int(input())
l = []

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

for i in range(1,11):
    l.append(f(10**i,n))
# print(l)
lf,ri = 0,0
for i in range(9):
    if l[i] <= s < l[i+1]:
        lf = 10**(i+1)
        ri = 10**(i+2)
else:
    lf = 2
    ri = 10

# print(lf,ri)

for b in range(lf, ri+1):
    if(f(b,n)==s):
        print(b)
        break
else:
    print(-1)

Submission status: Wrong Answer

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

n = int(input())
s = int(input())
l = []
for i in range(1,11):
    l.append(f(10**i,n))
# print(l)
lf,ri = 0,0
for i in range(9):
    if l[i] <= s < l[i+1]:
        lf = 10**(i+1)
        ri = 10**(i+2)
else:
    lf = 2
    ri = 10

# print(lf,ri)

for b in range(lf, ri+1):
    if(f(b,n)==s):
        print(b)
        break
else:
    print(-1)

Submission status: Wrong Answer

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

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

for b in range(2, 100000000000):
    if(f(b,n)==s):
        print(b)
        break
    if(b>=s or b>n and b!=s):
        print(-1)
        break
else:
    print(-1)

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+1):
        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:
            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 collections
N = int(input())
S = int(input())

if N == S > 1:
    print(N)
    exit()
elif N == S == 1:
    print(2)
    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: Wrong Answer

Solution code:
import collections
N = int(input())
S = int(input())
if N == S:
    print(N)
    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()
print(-1)

Submission status: Wrong Answer

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)


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: Wrong Answer

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)


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

Submission status: Wrong Answer

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

    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: Wrong Answer

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 s == 1:
        print(n)
        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:
            print(b)
            return

    print(-1)

if __name__ == '__main__':
    submit()

Submission status: Wrong Answer

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: Wrong Answer

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

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()
if s == 1:
    print(n)
    exit()
for i in range(1, int(n**0.5) + 10):
    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 f(b, n) == s and b>p and b>q:
        ans = min(ans, b)
if ans == 10**15:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

if s == 1:
    print(n)
    exit()
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**12
for i in range(2, int(n**0.5) + 1):
    if (n-s) % i == 0:
        b = (n-s) // i + 1
        if f(b, n) == s:
            ans = min(ans, b)
if ans == 10**12:
    print(-1)

Submission status: Wrong Answer

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

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

if s == 1:
    print(n)
    exit()
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**9
for i in range(2, int(n**0.5) + 1):
    if (n-s) % i == 0:
        b = (n-s) // i + 1
        if f(b, n) == s:
            ans = min(ans, b)
if ans == 10**9:
    print(-1)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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 -1
    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
    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):
            return b
    return -1

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

Submission status: Wrong Answer

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 -1
    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
    for p in range(1, m+10):
        q = s - p
        if (n - q) % p != 0:
            continue
        b = (n - q) // p
        if (b > p) and (b > 1) and (f(b, n) == s):
            return b
    return -1

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

Submission status: Wrong Answer

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 -1
    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+1):
        q = s - p
        if (n - q) % p != 0:
            continue
        b = (n - q) // p
        if (b > 1) and (f(b, n) == s):
            best = min(best, s)
    return -1 if (best == INF) else best

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

Submission status: Wrong Answer

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

def solve(n, s):
    if n < s:
        return -1
    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
    for p in range(1, m+1):
        q = s - p
        if (n - q) % p != 0:
            continue
        b = (n - q) // p
        if (b > 1) and (f(b, n) == s):
            return b
    return -1

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

Submission status: Wrong Answer

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

def solve(n, s):
    if n < s:
        return -1
    if n == s:
        return n+1
    m = int(np.sqrt(n)) + 1
    for b in range(2, m):
        if f(b, n) == s:
            return b
    for p in range(1, m):
        q = s - p
        if (n - q) % p != 0:
            continue
        b = (n - q) // p
        if (b > 1) and (f(b, n) == s):
            return b
    return -1

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

Submission status: Wrong Answer

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

def solve(n, s):
    m = int(np.sqrt(n)) + 1
    for b in range(2, m):
        if f(b, n) == s:
            return b
    for p in range(1, m):
        q = s - p
        if (n - q) % p != 0:
            continue
        b = (n - q) // p
        if (b > 1) and (f(b, n) == s):
            return b
    return -1

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