Count Subtractions

AtCoder

IDabc297_d

Time2000ms

Memory256MB

Difficulty—

You are given positive integers $A$ and $B$. You will repeat the following operation until $A=B$: * compare $A$ and $B$ to perform one of the following two: * if $A > B$, replace $A$ with $A-B$; * if $A < B$, replace $B$ with $B-A$. How many times will you repeat it until $A=B$? It is guaranteed that a finite repetition makes $A=B$. ## Constraints * $1 \le A,B \le 10^{18}$ * All values in the input are integers. ## Input The input is given from Standard Input in the following format: $A$ $B$ [samples]

Samples

Input #1

3 8

Output #1

4

Initially, $A=3$ and $B=8$. You repeat the operation as follows:

*   $A<B$, so replace $B$ with $B-A=5$, making $A=3$ and $B=5$.
*   $A<B$, so replace $B$ with $B-A=2$, making $A=3$ and $B=2$.
*   $A>B$, so replace $A$ with $A-B=1$, making $A=1$ and $B=2$.
*   $A<B$, so replace $B$ with $B-A=1$, making $A=1$ and $B=1$.

Thus, you repeat it four times.

Input #2

1234567890 1234567890

Output #2

0

Note that the input may not fit into a 32-bit integer type.

Input #3

1597 987

Output #3

API Response (JSON)

{
  "problem": {
    "name": "Count Subtractions",
    "description": {
      "content": "You are given positive integers $A$ and $B$. You will repeat the following operation until $A=B$: *   compare $A$ and $B$ to perform one of the following two:     *   if $A > B$, replace $A$ with $A-",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc297_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given positive integers $A$ and $B$.\nYou will repeat the following operation until $A=B$:\n\n*   compare $A$ and $B$ to perform one of the following two:\n    *   if $A > B$, replace $A$ with $A-...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments