B. Weird Subtraction Process

Codeforces

IDCF946B

Time1000ms

Memory256MB

Difficulty—

mathnumber theory

English · Original

Chinese · Translation

Formal · Original

You have two variables _a_ and _b_. Consider the following sequence of actions performed with these variables: 1. If _a_ = 0 or _b_ = 0, end the process. Otherwise, go to step 2; 2. If _a_ ≥ 2·_b_, then set the value of _a_ to _a_ - 2·_b_, and repeat step 1. Otherwise, go to step 3; 3. If _b_ ≥ 2·_a_, then set the value of _b_ to _b_ - 2·_a_, and repeat step 1. Otherwise, end the process. Initially the values of _a_ and _b_ are positive integers, and so the process will be finite. You have to determine the values of _a_ and _b_ after the process ends. ## Input The only line of the input contains two integers _n_ and _m_ (1 ≤ _n_, _m_ ≤ 1018). _n_ is the initial value of variable _a_, and _m_ is the initial value of variable _b_. ## Output Print two integers — the values of _a_ and _b_ after the end of the process. [samples] ## Note Explanations to the samples: 1. _a_ = 12, _b_ = 5 _a_ = 2, _b_ = 5 _a_ = 2, _b_ = 1 _a_ = 0, _b_ = 1; 2. _a_ = 31, _b_ = 12 _a_ = 7, _b_ = 12.

你有两个变量 #cf_span[a] 和 #cf_span[b]。考虑对这两个变量执行以下操作序列：最初，#cf_span[a] 和 #cf_span[b] 的值为正整数，因此该过程将是有限的。你需要确定过程结束时 #cf_span[a] 和 #cf_span[b] 的值。输入的唯一一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 1018]）。#cf_span[n] 是变量 #cf_span[a] 的初始值，#cf_span[m] 是变量 #cf_span[b] 的初始值。请输出两个整数——过程结束时 #cf_span[a] 和 #cf_span[b] 的值。样例解释： ## Input 输入的唯一一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 1018]）。#cf_span[n] 是变量 #cf_span[a] 的初始值，#cf_span[m] 是变量 #cf_span[b] 的初始值。 ## Output 请输出两个整数——过程结束时 #cf_span[a] 和 #cf_span[b] 的值。 [samples] ## Note 样例解释：#cf_span[a = 12], #cf_span[b = 5] #cf_span[a = 2], #cf_span[b = 5] #cf_span[a = 2], #cf_span[b = 1] #cf_span[a = 0], #cf_span[b = 1]；#cf_span[a = 31], #cf_span[b = 12] #cf_span[a = 7], #cf_span[b = 12]。

**Definitions** Let $ n, m \in \mathbb{Z}^+ $ be the initial values of variables $ a $ and $ b $, respectively. **Process** While $ a > 0 $ and $ b > 0 $: - If $ a \geq b $, set $ a \leftarrow a - b $. - Else, set $ b \leftarrow b - a $. **Constraints** $ 1 \leq n, m \leq 10^{18} $ **Objective** Compute the final values of $ a $ and $ b $ after the process terminates.

Samples

Input #1

12 5

Output #1

0 1

Input #2

31 12

Output #2

7 12

API Response (JSON)

{
  "problem": {
    "name": "B. Weird Subtraction Process",
    "description": {
      "content": "You have two variables _a_ and _b_. Consider the following sequence of actions performed with these variables: 1.  If _a_ = 0 or _b_ = 0, end the process. Otherwise, go to step 2; 2.  If _a_ ≥ 2·_b_,",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF946B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You have two variables _a_ and _b_. Consider the following sequence of actions performed with these variables:\n\n1.  If _a_ = 0 or _b_ = 0, end the process. Otherwise, go to step 2;\n2.  If _a_ ≥ 2·_b_,...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你有两个变量 #cf_span[a] 和 #cf_span[b]。考虑对这两个变量执行以下操作序列：\n\n最初，#cf_span[a] 和 #cf_span[b] 的值为正整数，因此该过程将是有限的。\n\n你需要确定过程结束时 #cf_span[a] 和 #cf_span[b] 的值。\n\n输入的唯一一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ be the initial values of variables $ a $ and $ b $, respectively.  \n\n**Process**  \nWhile $ a > 0 $ and $ b > 0 $:  \n- If $ a \\geq b $, set $ a \\leftarro...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments