A. k-Factorization

Codeforces

IDCF797A

Time2000ms

Memory256MB

Difficulty—

implementationmathnumber theory

English · Original

Chinese · Translation

Formal · Original

Given a positive integer _n_, find _k_ integers (not necessary distinct) such that all these integers are strictly greater than 1, and their product is equal to _n_. ## Input The first line contains two integers _n_ and _k_ (2 ≤ _n_ ≤ 100000, 1 ≤ _k_ ≤ 20). ## Output If it's impossible to find the representation of _n_ as a product of _k_ numbers, print _\-1_. Otherwise, print _k_ integers in any order. Their product must be equal to _n_. If there are multiple answers, print any of them. [samples]

给定一个正整数 $n$，找出 $k$ 个整数（不必互不相同），使得这些整数均严格大于 $1$，且它们的乘积等于 $n$。第一行包含两个整数 $n$ 和 $k$（$2 ≤ n ≤ 100000$，$1 ≤ k ≤ 20$）。如果无法将 $n$ 表示为 $k$ 个数的乘积，请输出 _-1_。否则，请输出 $k$ 个整数（顺序任意）。它们的乘积必须等于 $n$。如果有多个答案，输出任意一个即可。 ## Input 第一行包含两个整数 $n$ 和 $k$（$2 ≤ n ≤ 100000$，$1 ≤ k ≤ 20$）。 ## Output 如果无法将 $n$ 表示为 $k$ 个数的乘积，请输出 _-1_。否则，输出 $k$ 个整数（顺序任意）。它们的乘积必须等于 $n$。如果有多个答案，输出任意一个即可。 [samples]

**Definitions** Let $ n \in \mathbb{Z} $, $ k \in \mathbb{Z} $ be given integers with $ 2 \leq n \leq 100000 $, $ 1 \leq k \leq 20 $. **Objective** Find $ k $ integers $ a_1, a_2, \dots, a_k \in \mathbb{Z} $ such that: - $ a_i > 1 $ for all $ i \in \{1, \dots, k\} $, - $ \prod_{i=1}^k a_i = n $. If no such tuple exists, output $-1$.

Samples

Input #1

100000 2

Output #1

2 50000

Input #2

100000 20

Output #2

\-1

Input #3

1024 5

Output #3

2 64 2 2 2

API Response (JSON)

{
  "problem": {
    "name": "A. k-Factorization",
    "description": {
      "content": "Given a positive integer _n_, find _k_ integers (not necessary distinct) such that all these integers are strictly greater than 1, and their product is equal to _n_.",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF797A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Given a positive integer _n_, find _k_ integers (not necessary distinct) such that all these integers are strictly greater than 1, and their product is equal to _n_.\n\n## Input\n\nThe first line contains...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定一个正整数 $n$，找出 $k$ 个整数（不必互不相同），使得这些整数均严格大于 $1$，且它们的乘积等于 $n$。\n\n第一行包含两个整数 $n$ 和 $k$（$2 ≤ n ≤ 100000$，$1 ≤ k ≤ 20$）。\n\n如果无法将 $n$ 表示为 $k$ 个数的乘积，请输出 _-1_。\n\n否则，请输出 $k$ 个整数（顺序任意）。它们的乘积必须等于 $n$。如果有多个答案，输出任意一个即...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ k \\in \\mathbb{Z} $ be given integers with $ 2 \\leq n \\leq 100000 $, $ 1 \\leq k \\leq 20 $.  \n\n**Objective**  \nFind $ k $ integers $ a_1, a_2, \\dots, a_k \\i...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments