E. Vasya's Function

Codeforces

IDCF837E

Time1000ms

Memory256MB

Difficulty—

binary searchimplementationmath

English · Original

Chinese · Translation

Formal · Original

Vasya is studying number theory. He has denoted a function _f_(_a_, _b_) such that: * _f_(_a_, 0) = 0; * _f_(_a_, _b_) = 1 + _f_(_a_, _b_ - _gcd_(_a_, _b_)), where _gcd_(_a_, _b_) is the greatest common divisor of _a_ and _b_. Vasya has two numbers _x_ and _y_, and he wants to calculate _f_(_x_, _y_). He tried to do it by himself, but found out that calculating this function the way he wants to do that might take very long time. So he decided to ask you to implement a program that will calculate this function swiftly. ## Input The first line contains two integer numbers _x_ and _y_ (1 ≤ _x_, _y_ ≤ 1012). ## Output Print _f_(_x_, _y_). [samples]

Vasya 正在学习数论。他定义了一个函数 #cf_span[f(a, b)]，满足： Vasya 有两个数 #cf_span[x] 和 #cf_span[y]，他希望计算 #cf_span[f(x, y)]。他尝试自己计算，但发现按照他想要的方式计算这个函数可能需要非常长的时间。因此，他决定请你实现一个程序，以快速计算这个函数。第一行包含两个整数 #cf_span[x] 和 #cf_span[y]（#cf_span[1 ≤ x, y ≤ 1012]）。请输出 #cf_span[f(x, y)]。 ## Input 第一行包含两个整数 #cf_span[x] 和 #cf_span[y]（#cf_span[1 ≤ x, y ≤ 1012]）。 ## Output 请输出 #cf_span[f(x, y)]。 [samples]

**Definitions** Let $ f : \mathbb{Z}^+ \times \mathbb{Z}^+ \to \mathbb{Z}^+ $ be a function such that: $$ f(x, y) = \gcd(x, y) $$ **Constraints** 1. $ x, y \in \mathbb{Z}^+ $ 2. $ 1 \le x, y \le 10^{12} $ **Objective** Compute $ f(x, y) = \gcd(x, y) $.

Samples

Input #1

3 5

Output #1

Input #2

6 3

Output #2

API Response (JSON)

{
  "problem": {
    "name": "E. Vasya's Function",
    "description": {
      "content": "Vasya is studying number theory. He has denoted a function _f_(_a_, _b_) such that: *   _f_(_a_, 0) = 0; *   _f_(_a_, _b_) = 1 + _f_(_a_, _b_ - _gcd_(_a_, _b_)), where _gcd_(_a_, _b_) is the greatest",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF837E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Vasya is studying number theory. He has denoted a function _f_(_a_, _b_) such that:\n\n*   _f_(_a_, 0) = 0;\n*   _f_(_a_, _b_) = 1 + _f_(_a_, _b_ - _gcd_(_a_, _b_)), where _gcd_(_a_, _b_) is the greatest...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Vasya 正在学习数论。他定义了一个函数 #cf_span[f(a, b)]，满足：\n\nVasya 有两个数 #cf_span[x] 和 #cf_span[y]，他希望计算 #cf_span[f(x, y)]。他尝试自己计算，但发现按照他想要的方式计算这个函数可能需要非常长的时间。因此，他决定请你实现一个程序，以快速计算这个函数。\n\n第一行包含两个整数 #cf_span[x] 和 #cf_spa...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ f : \\mathbb{Z}^+ \\times \\mathbb{Z}^+ \\to \\mathbb{Z}^+ $ be a function such that:  \n$$ f(x, y) = \\gcd(x, y) $$\n\n**Constraints**  \n1. $ x, y \\in \\mathbb{Z}^+ $  \n2. $ 1 \\le x, y ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments