← 返回题目列表

Codeforces · 933/B

B. 坚决清理

中文机器翻译题面 查看原题

为了收拾旧物,迎接崭新的一年,彻底的房屋大扫除是必须的。

小汤米找到了一个旧多项式,并通过对另一个多项式取模来清理它。但现在他却后悔这么做了……

给定两个整数 p 和 k,找到一个非负整数系数严格小于 k 的多项式 f(x),除以 (x + k) 时余数为 p。即,f(x) = q(x)·(x + k) + p,其中q(x) 是多项式(不一定具有整数系数)。

输入

输入的唯一一行包含两个空格分隔的整数 p 和 k (1 ≤ p ≤ 1018, 2 ≤ k ≤ 2 000)。

输出

如果多项式不存在,则打印单个整数-1,否则输出两行。

在第一行中打印一个非负整数 d — 多项式中的系数数量。

在第二行中打印 d 个空格分隔的整数 a0, a1, ..., ad - 1,描述满足给定要求的多项式 $$f(x) = \sum_{i=0}^{d-1} a_i \cdot x^i$$。对于所有 0 ≤ i ≤ d - 1,并且 ad - 1 ≠ 0,您的输出应满足 0 ≤ ai < k。

如果有多种可能的解决方案,请打印其中任何一个。

示例

输入 #1

46 2

输出 #1

7
0 1 0 0 1 1 1

输入 #2

2018 214

输出 #2

3
92 205 1

注意

在第一个示例中,f(x) = x6 + x5 + x4 + x = (x5 - x4 + 3x3 - 6x2 + 12x - 23)·(x + 2) + 46。

在第二个示例中,f(x) = x2 + 205x + 92 = (x - 9)·(x + 214) + 2018。