【Codeforces Round #462 (Div. 1) B】A Determined Cleanup

在这里输入题意

【题解】

设$设f(x)=a_d*x^{d}+a_{d-1}*x^{d-1}+...+a_1*x+a_0$
用它去除x+k
用多项式除法除一下就好。
会发现余数等于
$∑_0^{d}(-k)^{i}*a_i$
这是一个十进制数转成负k进制数的和的形式。
而p已知。
问题就转化为把十进制数p转成-k进制数的问题了。

【代码】

#include <bits/stdc++.h>

#define ll long long

using namespace std;

ll p,k;

vector<int> v;

int main(){

	#ifdef LOCAL_DEFINE

	    freopen("rush_in.txt", "r", stdin);

	#endif

	ios::sync_with_stdio(0),cin.tie(0);

    cin >> p >> k;

    k = -k;

    while (p!=0){

        int x = p%k;

        p/=k;

        if (x<0) {

            x+=abs(k);

            p++;

        }

        v.push_back(x);

    }

    cout<<(int)v.size()<<endl;

    for (int x:v)

        cout<<x<<' ';

	return 0;

}

巴特西

【Codeforces Round #462 (Div. 1) B】A Determined Cleanup

最新文章

热门文章