Digit Sum

AtCoder

IDarc060_b

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

87654
30

Output #1

Input #2

87654
138

Output #2

Input #3

87654
45678

Output #3

\-1

Input #4

31415926535
1

Output #4

31415926535

Input #5

1
31415926535

Output #5

\-1

API Response (JSON)

{
  "problem": {
    "name": "Digit Sum",
    "description": {
      "content": "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",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc060_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "For integers $b (b \\geq 2)$ and $n (n \\geq 1)$, let the function $f(b,n)$ be defined as follows:\n\n*   $f(b,n) = n$, when $n < b$\n*   $f(b,n) = f(b,\\,{\\rm floor}(n / b)) + (n \\ {\\rm mod} \\ b)$, when $n...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments