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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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;
}

------ 本文结束 ------