G. List Of Integers

Codeforces

IDCF920G

Time5000ms

Memory256MB

Difficulty—

binary searchbitmasksbrute forcecombinatoricsmathnumber theory

English · Original

Chinese · Translation

Formal · Original

Let's denote as _L_(_x_, _p_) an infinite sequence of integers _y_ such that _gcd_(_p_, _y_) = 1 and _y_ > _x_ (where _gcd_ is the greatest common divisor of two integer numbers), sorted in ascending order. The elements of _L_(_x_, _p_) are 1\-indexed; for example, 9, 13 and 15 are the first, the second and the third elements of _L_(7, 22), respectively. You have to process _t_ queries. Each query is denoted by three integers _x_, _p_ and _k_, and the answer to this query is _k_\-th element of _L_(_x_, _p_). ## Input The first line contains one integer _t_ (1 ≤ _t_ ≤ 30000) — the number of queries to process. Then _t_ lines follow. _i_\-th line contains three integers _x_, _p_ and _k_ for _i_\-th query (1 ≤ _x_, _p_, _k_ ≤ 106). ## Output Print _t_ integers, where _i_\-th integer is the answer to _i_\-th query. [samples]

我们定义 #cf_span[L(x, p)] 为一个无限整数序列 #cf_span[y]，满足 #cf_span[gcd(p, y) = 1] 且 #cf_span[y > x]（其中 #cf_span[gcd] 表示两个整数的最大公约数），并将这些整数按升序排列。序列 #cf_span[L(x, p)] 的元素是 #cf_span[1]-索引的；例如，#cf_span[9]、#cf_span[13] 和 #cf_span[15] 分别是 #cf_span[L(7, 22)] 的第一个、第二个和第三个元素。你需要处理 #cf_span[t] 个查询。每个查询由三个整数 #cf_span[x]、#cf_span[p] 和 #cf_span[k] 表示，该查询的答案是 #cf_span[L(x, p)] 的第 #cf_span[k] 个元素。第一行包含一个整数 #cf_span[t] (#cf_span[1 ≤ t ≤ 30000]) —— 需要处理的查询数量。接下来 #cf_span[t] 行，每行包含三个整数 #cf_span[x]、#cf_span[p] 和 #cf_span[k]，表示第 #cf_span[i] 个查询 (#cf_span[1 ≤ x, p, k ≤ 106])。请输出 #cf_span[t] 个整数，其中第 #cf_span[i] 个整数是第 #cf_span[i] 个查询的答案。 ## Input 第一行包含一个整数 #cf_span[t] (#cf_span[1 ≤ t ≤ 30000]) —— 需要处理的查询数量。接下来 #cf_span[t] 行，每行包含三个整数 #cf_span[x]、#cf_span[p] 和 #cf_span[k]，表示第 #cf_span[i] 个查询 (#cf_span[1 ≤ x, p, k ≤ 106])。 ## Output 请输出 #cf_span[t] 个整数，其中第 #cf_span[i] 个整数是第 #cf_span[i] 个查询的答案。 [samples]

**Definitions** Let $ L(x, p) $ be the infinite sequence of integers $ y $ such that $ y > x $ and $ \gcd(y, p) = 1 $, sorted in ascending order. The sequence is 1-indexed. **Constraints** 1. $ 1 \le t \le 30000 $ 2. For each query: $ 1 \le x, p, k \le 10^6 $ **Objective** For each query $ (x, p, k) $, compute the $ k $-th element of $ L(x, p) $, i.e., the $ k $-th smallest integer $ y > x $ such that $ \gcd(y, p) = 1 $.

Samples

Input #1

Output #1

9
13
15

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "G. List Of Integers",
    "description": {
      "content": "Let's denote as _L_(_x_, _p_) an infinite sequence of integers _y_ such that _gcd_(_p_, _y_) = 1 and _y_ > _x_ (where _gcd_ is the greatest common divisor of two integer numbers), sorted in ascending ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF920G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Let's denote as _L_(_x_, _p_) an infinite sequence of integers _y_ such that _gcd_(_p_, _y_) = 1 and _y_ > _x_ (where _gcd_ is the greatest common divisor of two integer numbers), sorted in ascending ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "我们定义 #cf_span[L(x, p)] 为一个无限整数序列 #cf_span[y]，满足 #cf_span[gcd(p, y) = 1] 且 #cf_span[y > x]（其中 #cf_span[gcd] 表示两个整数的最大公约数），并将这些整数按升序排列。序列 #cf_span[L(x, p)] 的元素是 #cf_span[1]-索引的；例如，#cf_span[9]、#cf_span[1...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ L(x, p) $ be the infinite sequence of integers $ y $ such that $ y > x $ and $ \\gcd(y, p) = 1 $, sorted in ascending order. The sequence is 1-indexed.\n\n**Constraints**  \n1. $ 1...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments