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 p and kk , find a polynomial f(x) f ( x ) with non-negative integer coefficients strictly less than k k , whose remainder is pp when divided by (x + k) ( x + k ) . That is, f(x) = q(x)⋅(x + k) + p f ( x ) = q ( x ) · ( x + k ) + p , where q(x) q ( x ) is a polynomial (not necessarily with integer coefficients).
The only line of input contains two space-separated integers p p and kk (1 ≤ p ≤ 1018,2 ≤ k ≤ 2 000) ( 1 ≤ p ≤ 10 18 , 2 ≤ k ≤ 2 000 ) .
If the polynomial does not exist, print a single integer −1 − 1 , or output two lines otherwise.
In the first line print a non-negative integer d d — the number of coefficients in the polynomial.
In the second line print dd space-separated integers a0, a1, ..., ad − 1 a 0 , a 1 , . . . , a d − 1 , describing a polynomial f(x)=∑d−1i=0ai⋅xi f ( x ) = ∑ i = 0 d − 1 a i · x i fulfilling the given requirements. Your output should satisfy 0 ≤ ai < k 0 ≤ a i < k for all 0 ≤ i ≤ d − 1 0 ≤ i ≤ d − 1 , and ad − 1 ≠ 0 a d − 1 ≠ 0 .
If there are many possible solutions, print any of them.
给定正整数 p,k p , k ，我们需要找出一个多项式 q(x) q ( x ) ，使得 f(x) = q(x)⋅(x + k) + p f ( x ) = q ( x ) · ( x + k ) + p 的各项系数严格小于 k k 且不为负数，输出 f(x)f(x) 的各项系数。
仔细想想便可以知道，这样的解一定是存在的，所以没有输出 −1 − 1 的可能性
我们可以对原式化简一下： f(x)=x⋅q(x)+k⋅q(x)+p f ( x ) = x · q ( x ) + k · q ( x ) + p
假设 q(x)=a1+a2⋅x+a3⋅x2+⋯+an⋅xn−1 q ( x ) = a 1 + a 2 · x + a 3 · x 2 + ⋯ + a n · x n − 1 ，其中 ai a i 为某一整数
现在我们再来讨论 f(x) f ( x ) 各项的系数：
常数项： k×a1+p k × a 1 + p 一次项： k×a2+a1 k × a 2 + a 1 二次项： k×a3+a2 k × a 3 + a 2 …于是我们有了一个通项不等式： 0≤k×an+an−1<k 0 ≤ k × a n + a n − 1 < k ，其中 a0=p a 0 = p
从上到下一一解出每一项即可，注意要保证系数不为负数
