D. A Determined Cleanup

Codeforces

IDCF934D

Time1000ms

Memory256MB

Difficulty—

math

English · Original

Chinese · Translation

Formal · Original

_In order to put away old things and welcome a fresh new year, a thorough cleaning of the house is a must._ Little Tommy finds an old polynomial and cleaned it up by taking it modulo another. But now he regrets doing this... Given two integers _p_ and _k_, find a polynomial _f_(_x_) with non-negative integer coefficients strictly less than _k_, whose remainder is _p_ when divided by (_x_ + _k_). That is, _f_(_x_) = _q_(_x_)·(_x_ + _k_) + _p_, where _q_(_x_) is a polynomial (not necessarily with integer coefficients). ## Input The only line of input contains two space-separated integers _p_ and _k_ (1 ≤ _p_ ≤ 1018, 2 ≤ _k_ ≤ 2 000). ## Output If the polynomial does not exist, print a single integer _\-1_, or output two lines otherwise. In the first line print a non-negative integer _d_ — the number of coefficients in the polynomial. In the second line print _d_ space-separated integers _a_0, _a_1, ..., _a__d_ - 1, describing a polynomial fulfilling the given requirements. Your output should satisfy 0 ≤ _a__i_ < _k_ for all 0 ≤ _i_ ≤ _d_ - 1, and _a__d_ - 1 ≠ 0. If there are many possible solutions, print any of them. [samples] ## Note In the first example, _f_(_x_) = _x_6 + _x_5 + _x_4 + _x_ = (_x_5 - _x_4 + 3_x_3 - 6_x_2 + 12_x_ - 23)·(_x_ + 2) + 46. In the second example, _f_(_x_) = _x_2 + 205_x_ + 92 = (_x_ - 9)·(_x_ + 214) + 2018.

为了整理旧物并迎接崭新的新年，彻底打扫房屋是必不可少的。小汤米找到了一个旧多项式，并通过对其取模另一个多项式进行了清理。但现在他后悔这样做了…… 给定两个整数 $p$ 和 $k$，找出一个系数为非负整数且严格小于 $k$ 的多项式 $f(x)$，使得它除以 $(x + k)$ 的余数为 $p$。即，$f(x) = q(x)·(x + k) + p$，其中 $q(x)$ 是一个多项式（不一定具有整数系数）。输入仅有一行，包含两个用空格分隔的整数 $p$ 和 $k$（$1 ≤ p ≤ 10^{18}$，$2 ≤ k ≤ 2 000$）。如果该多项式不存在，请输出单个整数 _-1_；否则，请输出两行。第一行输出一个非负整数 $d$ —— 多项式的系数个数。第二行输出 $d$ 个用空格分隔的整数 $a_0, a_1, ..., a_{d - 1}$，描述一个满足要求的多项式。你的输出需满足对所有 $0 ≤ i ≤ d - 1$，有 $0 ≤ a_i < k$，且 $a_{d - 1} ≠ 0$。如果存在多个可能的解，请输出任意一个。在第一个例子中，$f(x) = x^6 + x^5 + x^4 + x = (x^5 - x^4 + 3x^3 - 6x^2 + 12x - 23)·(x + 2) + 46$。在第二个例子中，$f(x) = x^2 + 205x + 92 = (x - 9)·(x + 214) + 2018$。 ## Input 输入仅有一行，包含两个用空格分隔的整数 $p$ 和 $k$（$1 ≤ p ≤ 10^{18}$，$2 ≤ k ≤ 2 000$）。 ## Output 如果该多项式不存在，请输出单个整数 _-1_；否则，请输出两行。第一行输出一个非负整数 $d$ —— 多项式的系数个数。第二行输出 $d$ 个用空格分隔的整数 $a_0, a_1, ..., a_{d - 1}$，描述一个满足要求的多项式。你的输出需满足对所有 $0 ≤ i ≤ d - 1$，有 $0 ≤ a_i < k$，且 $a_{d - 1} ≠ 0$。如果存在多个可能的解，请输出任意一个。 [samples] ## Note 在第一个例子中，$f(x) = x^6 + x^5 + x^4 + x = (x^5 - x^4 + 3x^3 - 6x^2 + 12x - 23)·(x + 2) + 46$。在第二个例子中，$f(x) = x^2 + 205x + 92 = (x - 9)·(x + 214) + 2018$。

**Definitions** Let $ p \in \mathbb{Z} $, $ k \in \mathbb{Z} $ with $ 1 \leq p \leq 10^{18} $, $ 2 \leq k \leq 2000 $. Let $ f(x) = \sum_{i=0}^{d-1} a_i x^i $ be a polynomial with coefficients $ a_i \in \mathbb{Z} $, $ 0 \leq a_i < k $, and $ a_{d-1} \neq 0 $. **Constraint** $ f(-k) = p $ **Objective** Find coefficients $ a_0, a_1, \dots, a_{d-1} $ such that: $$ f(-k) = \sum_{i=0}^{d-1} a_i (-k)^i = p $$ If no such polynomial exists, output $-1$. Otherwise, output $ d $ and the sequence $ a_0, a_1, \dots, a_{d-1} $.

Samples

Input #1

46 2

Output #1

7
0 1 0 0 1 1 1

Input #2

2018 214

Output #2

3
92 205 1

API Response (JSON)

{
  "problem": {
    "name": "D. A Determined Cleanup",
    "description": {
      "content": "_In order to put away old things and welcome a fresh new year, a thorough cleaning of the house is a must._ Little Tommy finds an old polynomial and cleaned it up by taking it modulo another. But now",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF934D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "_In order to put away old things and welcome a fresh new year, a thorough cleaning of the house is a must._\n\nLittle Tommy finds an old polynomial and cleaned it up by taking it modulo another. But now...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "为了整理旧物并迎接崭新的新年，彻底打扫房屋是必不可少的。\n\n小汤米找到了一个旧多项式，并通过对其取模另一个多项式进行了清理。但现在他后悔这样做了……\n\n给定两个整数 $p$ 和 $k$，找出一个系数为非负整数且严格小于 $k$ 的多项式 $f(x)$，使得它除以 $(x + k)$ 的余数为 $p$。即，$f(x) = q(x)·(x + k) + p$，其中 $q(x)$ 是一个多项式（不一定具...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ p \\in \\mathbb{Z} $, $ k \\in \\mathbb{Z} $ with $ 1 \\leq p \\leq 10^{18} $, $ 2 \\leq k \\leq 2000 $.  \nLet $ f(x) = \\sum_{i=0}^{d-1} a_i x^i $ be a polynomial with coefficients $ a...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments