A. k-th divisor

Codeforces

IDCF762A

Time2000ms

Memory256MB

Difficulty—

mathnumber theory

English · Original

Chinese · Translation

Formal · Original

You are given two integers _n_ and _k_. Find _k_\-th smallest divisor of _n_, or report that it doesn't exist. Divisor of _n_ is any such natural number, that _n_ can be divided by it without remainder. ## Input The first line contains two integers _n_ and _k_ (1 ≤ _n_ ≤ 1015, 1 ≤ _k_ ≤ 109). ## Output If _n_ has less than _k_ divisors, output _\-1_. Otherwise, output the _k_\-th smallest divisor of _n_. [samples] ## Note In the first example, number 4 has three divisors: 1, 2 and 4. The second one is 2. In the second example, number 5 has only two divisors: 1 and 5. The third divisor doesn't exist, so the answer is _\-1_.

给定两个整数 $n$ 和 $k$。求 $n$ 的第 $k$ 小的约数，若不存在则报告。 $n$ 的约数是指任何自然数，使得 $n$ 能被其整除而无余数。第一行包含两个整数 $n$ 和 $k$（$1 ≤ n ≤ 10^{15}$，$1 ≤ k ≤ 10^9$）。如果 $n$ 的约数个数少于 $k$ 个，请输出 _-1_。否则，输出 $n$ 的第 $k$ 小的约数。在第一个例子中，数字 $4$ 有三个约数：$1$、$2$ 和 $4$。第二个是 $2$。在第二个例子中，数字 $5$ 只有两个约数：$1$ 和 $5$。第三个约数不存在，因此答案为 _-1_。 ## Input 第一行包含两个整数 $n$ 和 $k$（$1 ≤ n ≤ 10^{15}$，$1 ≤ k ≤ 10^9$）。 ## Output 如果 $n$ 的约数个数少于 $k$ 个，请输出 _-1_。否则，输出 $n$ 的第 $k$ 小的约数。 [samples] ## Note 在第一个例子中，数字 $4$ 有三个约数：$1$、$2$ 和 $4$。第二个是 $2$。在第二个例子中，数字 $5$ 只有两个约数：$1$ 和 $5$。第三个约数不存在，因此答案为 _-1_。

**Definitions** Let $ n \in \mathbb{Z}^+ $ with $ 1 \leq n \leq 10^{15} $. Let $ D(n) = \{ d \in \mathbb{Z}^+ \mid d \mid n \} $ be the set of positive divisors of $ n $, ordered increasingly: $ d_1 < d_2 < \dots < d_{\tau(n)} $, where $ \tau(n) = |D(n)| $. Let $ k \in \mathbb{Z}^+ $ with $ 1 \leq k \leq 10^9 $. **Constraints** $ 1 \leq n \leq 10^{15} $, $ 1 \leq k \leq 10^9 $. **Objective** If $ k > \tau(n) $, output $ -1 $. Otherwise, output $ d_k $, the $ k $-th smallest positive divisor of $ n $.

Samples

Input #1

4 2

Output #1

Input #2

5 3

Output #2

\-1

Input #3

12 5

Output #3

API Response (JSON)

{
  "problem": {
    "name": "A. k-th divisor",
    "description": {
      "content": "You are given two integers _n_ and _k_. Find _k_\\-th smallest divisor of _n_, or report that it doesn't exist. Divisor of _n_ is any such natural number, that _n_ can be divided by it without remaind",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF762A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given two integers _n_ and _k_. Find _k_\\-th smallest divisor of _n_, or report that it doesn't exist.\n\nDivisor of _n_ is any such natural number, that _n_ can be divided by it without remaind...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定两个整数 $n$ 和 $k$。求 $n$ 的第 $k$ 小的约数，若不存在则报告。\n\n$n$ 的约数是指任何自然数，使得 $n$ 能被其整除而无余数。\n\n第一行包含两个整数 $n$ 和 $k$（$1 ≤ n ≤ 10^{15}$，$1 ≤ k ≤ 10^9$）。\n\n如果 $n$ 的约数个数少于 $k$ 个，请输出 _-1_。\n\n否则，输出 $n$ 的第 $k$ 小的约数。\n\n在第一个例子中，数...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ with $ 1 \\leq n \\leq 10^{15} $.  \nLet $ D(n) = \\{ d \\in \\mathbb{Z}^+ \\mid d \\mid n \\} $ be the set of positive divisors of $ n $, ordered increasingly: $ d...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments