C. Maximal GCD

Codeforces

IDCF803C

Time1000ms

Memory256MB

Difficulty—

constructive algorithmsgreedymath

English · Original

Chinese · Translation

Formal · Original

You are given positive integer number _n_. You should create such **strictly increasing** sequence of _k_ positive numbers _a_1, _a_2, ..., _a__k_, that their sum is equal to _n_ and greatest common divisor is maximal. Greatest common divisor of sequence is maximum of such numbers that every element of sequence is divisible by them. If there is no possible sequence then output _\-1_. ## Input The first line consists of two numbers _n_ and _k_ (1 ≤ _n_, _k_ ≤ 1010). ## Output If the answer exists then output _k_ numbers — resulting sequence. Otherwise output _\-1_. If there are multiple answers, print any of them. [samples]

给定一个正整数 $n$。你需要构造一个由 $k$ 个正整数构成的*严格递增*序列 $a_1, a_2, ..., a_k$，使得它们的和等于 $n$，且它们的最大公约数尽可能大。序列的最大公约数定义为：能整除序列中每一个元素的最大正整数。如果不存在这样的序列，则输出 _-1_。第一行包含两个数 $n$ 和 $k$（$1 ≤ n, k ≤ 10^{10}$）。如果答案存在，则输出 $k$ 个数——即所求序列。否则输出 _-1_。如果有多个答案，输出任意一个即可。 ## Input 第一行包含两个数 $n$ 和 $k$（$1 ≤ n, k ≤ 10^{10}$）。 ## Output 如果答案存在，则输出 $k$ 个数——即所求序列。否则输出 _-1_。如果有多个答案，输出任意一个即可。 [samples]

**Definitions** Let $ n, k \in \mathbb{Z}^+ $ with $ 1 \leq n, k \leq 10^{10} $. Let $ A = (a_1, a_2, \dots, a_k) $ be a strictly increasing sequence of positive integers such that $ \sum_{i=1}^k a_i = n $. **Constraints** 1. $ a_1 < a_2 < \dots < a_k $ 2. $ a_i \in \mathbb{Z}^+ $ for all $ i \in \{1, \dots, k\} $ 3. $ \sum_{i=1}^k a_i = n $ **Objective** Maximize $ d = \gcd(a_1, a_2, \dots, a_k) $ over all valid sequences $ A $. If no such sequence exists, output $-1$. Otherwise, output any sequence $ A $ achieving the maximum $ d $.

Samples

Input #1

6 3

Output #1

1 2 3

Input #2

8 2

Output #2

2 6

Input #3

5 3

Output #3

\-1

API Response (JSON)

{
  "problem": {
    "name": "C. Maximal GCD",
    "description": {
      "content": "You are given positive integer number _n_. You should create such **strictly increasing** sequence of _k_ positive numbers _a_1, _a_2, ..., _a__k_, that their sum is equal to _n_ and greatest common d",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF803C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given positive integer number _n_. You should create such **strictly increasing** sequence of _k_ positive numbers _a_1, _a_2, ..., _a__k_, that their sum is equal to _n_ and greatest common d...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定一个正整数 $n$。你需要构造一个由 $k$ 个正整数构成的*严格递增*序列 $a_1, a_2, ..., a_k$，使得它们的和等于 $n$，且它们的最大公约数尽可能大。\n\n序列的最大公约数定义为：能整除序列中每一个元素的最大正整数。\n\n如果不存在这样的序列，则输出 _-1_。\n\n第一行包含两个数 $n$ 和 $k$（$1 ≤ n, k ≤ 10^{10}$）。\n\n如果答案存在，则输出 $...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k \\in \\mathbb{Z}^+ $ with $ 1 \\leq n, k \\leq 10^{10} $.  \nLet $ A = (a_1, a_2, \\dots, a_k) $ be a strictly increasing sequence of positive integers such that $ \\sum_{i=1}^k ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments