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$，请找出一个多项式 $f(x)$，其系数均为非负整数且严格小于 $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 $.
**Objective**
Find a polynomial $ f(x) = a_0 + a_1 x + a_2 x^2 + \dots + a_{d-1} x^{d-1} $ with integer coefficients $ a_i \in \mathbb{Z} $, such that:
- $ 0 \leq a_i < k $ for all $ i \in \{0, 1, \dots, d-1\} $,
- $ a_{d-1} \neq 0 $,
- $ f(-k) = p $.
Equivalently, find coefficients $ a_0, a_1, \dots, a_{d-1} \in \{0, 1, \dots, k-1\} $, not all zero, such that:
$$
\sum_{i=0}^{d-1} a_i (-k)^i = p
$$
If no such polynomial exists, output $-1$.
API Response (JSON)
{
"problem": {
"name": "B. 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": "CF933B"
},
"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$，请找出一个多项式 $f(x)$，其系数均为非负整数且严格小于 $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 $. \n\n**Objective** \nFind a polynomial $ f(x) = a_0 + a_1 x + a_2 x^2 + \\dots + a...",
"is_translate": false,
"language": "Formal"
}
]
}