C. Modified GCD

Codeforces

IDCF75C

Time2000ms

Memory256MB

Difficulty—

binary searchnumber theory

English · Original

Chinese · Translation

Formal · Original

Well, here is another math class task. In mathematics, GCD is the greatest common divisor, and it's an easy task to calculate the GCD between two positive integers. A common divisor for two positive numbers is a number which both numbers are divisible by. But your teacher wants to give you a harder task, in this task you have to find the greatest common divisor _d_ between two integers _a_ and _b_ that is in a given range from _low_ to _high_ (inclusive), i.e. _low_ ≤ _d_ ≤ _high_. It is possible that there is no common divisor in the given range. You will be given the two integers _a_ and _b_, then _n_ queries. Each query is a range from _low_ to _high_ and you have to answer each query. ## Input The first line contains two integers _a_ and _b_, the two integers as described above (1 ≤ _a_, _b_ ≤ 109). The second line contains one integer _n_, the number of queries (1 ≤ _n_ ≤ 104). Then _n_ lines follow, each line contains one query consisting of two integers, _low_ and _high_ (1 ≤ _low_ ≤ _high_ ≤ 109). ## Output Print _n_ lines. The _i_\-th of them should contain the result of the _i_\-th query in the input. If there is no common divisor in the given range for any query, you should print _\-1_ as a result for this query. [samples]

好吧，这是另一个数学课的题目。在数学中，GCD 是最大公约数，计算两个正整数的 GCD 是一件简单的事。两个正数的公约数是指能同时整除这两个数的数。但你的老师想给你一个更难的任务：在这个任务中，你需要在给定的范围 [low, high]（包含端点）内找到两个整数 a 和 b 的最大公约数 d，即满足 low ≤ d ≤ high。可能在该范围内不存在任何公约数。你将得到两个整数 a 和 b，然后是 n 个查询。每个查询是一个从 low 到 high 的范围，你需要对每个查询给出答案。第一行包含两个整数 a 和 b（1 ≤ a, b ≤ 10^9）。第二行包含一个整数 n（1 ≤ n ≤ 10^4），表示查询的数量。接下来 n 行，每行包含一个查询，由两个整数 low 和 high 组成（1 ≤ low ≤ high ≤ 10^9）。请输出 n 行。第 i 行应包含输入中第 i 个查询的结果。如果某个查询在给定范围内没有公约数，则应输出 _-1_ 作为该查询的结果。 ## Input 第一行包含两个整数 a 和 b（1 ≤ a, b ≤ 10^9）。第二行包含一个整数 n（1 ≤ n ≤ 10^4），表示查询的数量。接下来 n 行，每行包含一个查询，由两个整数 low 和 high 组成（1 ≤ low ≤ high ≤ 10^9）。 ## Output 请输出 n 行。第 i 行应包含输入中第 i 个查询的结果。如果某个查询在给定范围内没有公约数，则应输出 _-1_ 作为该查询的结果。 [samples]

**Definitions** Let $ a, b \in \mathbb{Z}^+ $ with $ 1 \le a, b \le 10^9 $. Let $ D = \{ d \in \mathbb{Z}^+ \mid d \mid a \text{ and } d \mid b \} $ be the set of common positive divisors of $ a $ and $ b $. Let $ g = \gcd(a, b) $. Then $ D = \{ d \in \mathbb{Z}^+ \mid d \mid g \} $. Let $ n \in \mathbb{Z}^+ $ with $ 1 \le n \le 10^4 $ be the number of queries. For each query $ i \in \{1, \dots, n\} $, let $ [l_i, h_i] $ be a range with $ 1 \le l_i \le h_i \le 10^9 $. **Constraints** 1. $ 1 \le a, b \le 10^9 $ 2. $ 1 \le n \le 10^4 $ 3. For each query $ i $: $ 1 \le l_i \le h_i \le 10^9 $ **Objective** For each query $ i \in \{1, \dots, n\} $, find: $$ \max \{ d \in D \mid l_i \le d \le h_i \} $$ If no such $ d $ exists, output $ -1 $.

Samples

Input #1

Output #1

3
-1
9

API Response (JSON)

{
  "problem": {
    "name": "C. Modified GCD",
    "description": {
      "content": "Well, here is another math class task. In mathematics, GCD is the greatest common divisor, and it's an easy task to calculate the GCD between two positive integers. A common divisor for two positive ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF75C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Well, here is another math class task. In mathematics, GCD is the greatest common divisor, and it's an easy task to calculate the GCD between two positive integers.\n\nA common divisor for two positive ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "好吧，这是另一个数学课的题目。在数学中，GCD 是最大公约数，计算两个正整数的 GCD 是一件简单的事。\n\n两个正数的公约数是指能同时整除这两个数的数。\n\n但你的老师想给你一个更难的任务：在这个任务中，你需要在给定的范围 [low, high]（包含端点）内找到两个整数 a 和 b 的最大公约数 d，即满足 low ≤ d ≤ high。可能在该范围内不存在任何公约数。\n\n你将得到两个整数 a 和...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ a, b \\in \\mathbb{Z}^+ $ with $ 1 \\le a, b \\le 10^9 $.  \nLet $ D = \\{ d \\in \\mathbb{Z}^+ \\mid d \\mid a \\text{ and } d \\mid b \\} $ be the set of common positive divisors of $ a $...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments