Codeforces 934D(数学)

Codeforces 934D
题意：给出$k,p$, 求多项式$f(x)$使得$f(x) = q(x) \cdot (x + k) + p$成立，输出$f(x)$多项式系数(系数必须为非负数以及小于$k$)

方法1：设$f(x)$和$q(x)$的系数，代换后发现$p$是进制形式的多项式，所以直接转化$p$为$-k$进制数即可
方法2：余式定理。$f(x)$除以$(x-k)$的多项式余数为$f(k)$，则$f(x)$除以$(x+k)$的多项式余数为$p$，所以$f(-k)=p$，可以将$p$转化为$-k$进制的数即可

注意：负进制的除法要严格向下取整。(默认靠0)。并且系数都要大于0，模时注意

Codeforces Submission

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
#define ms(i, j) memset(i, j, sizeof i)
#define ll long long
#define db double
ll p, k;
vector<int> vec;
void clean() {
}
int solve() {
    clean();
    while (p != 0) {
        vec.push_back((p % k + k) % k);
        p = (vec.back() - p) / k;
    }
    printf("%d\n", vec.size());
    for (int i = 0; i < (int)vec.size(); i++) printf("%d ", vec[i]);
    return 0;
}
int main() {
    scanf("%I64d%I64d", &p, &k), solve();
    return 0;
}