Description

给你两个正整数 \(p,k\) ，询问是否能够构造多项式 \(f(x)=\sum\limits_{i=0}^{d-1}a_ix^i\) ，使得存在多项式 \(q(x)\) ，满足 \(f(x)=q(x)\cdot(x+k)+p\) 。且 \(a_i\in[0,k),i\in [0,d)\) 。

\(1\leq p\leq 10^{18},2\leq k\leq 2000\)

Solution

我们假设 \(q(x)=\sum\limits_{i=0}^{d-2}b_ix^i\) ，那么存在 \[\begin{aligned}a_0&=kb_0+p\\a_1&=kb_1+b_0\\&\vdots\\a_{d-2}&=kb_{d-2}+b_{d-3}\\a_{d-1}&=b_{d-2}\end{aligned}\]

逐步从下往上递推，最终我们可以得到 \(p=\sum\limits_{i=0}^{d-1} (-k)^ia_i\) 。显然 \(p_{(10)}=\overline{a_{d-1}\cdots a_1a_0}_{(-k)}\) ，做一遍进制转换就好了。

Code

//It is made by Awson on 2018.2.17#include 
    
     #define LL long long#define dob complex
     
      #define Abs(a) ((a) < 0 ? (-(a)) : (a))#define Max(a, b) ((a) > (b) ? (a) : (b))#define Min(a, b) ((a) < (b) ? (a) : (b))#define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))#define writeln(x) (write(x), putchar('\n'))#define lowbit(x) ((x)&(-(x)))using namespace std;void read(LL &x) {    char ch; bool flag = 0;    for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || 1); ch = getchar());    for (x = 0; isdigit(ch); x = (x<<1)+(x<<3)+ch-48, ch = getchar());    x *= 1-2*flag;}void print(LL x) {if (x > 9) print(x/10); putchar(x%10+48); }void write(LL x) {if (x < 0) putchar('-'); print(Abs(x)); }LL p, k, a[10005], d;void work() {    read(p), read(k); k = -k;    while (p) {        a[++d] = p%k, p /= k;         if (a[d] < 0) a[d] = -k+a[d], p++;    }    writeln(d);    for (int i = 1; i <= d; i++) write(a[i]), putchar(' ');}int main() {    work(); return 0;}