A Determined Cleanup [Codeforces Round #462 (Div. 1) B]

http://codeforces.com/contest/933/problem/B

P,Kが与えられる。
f(x) = q(x)*(x+K)+Pが成り立つようにf(x)を求めよ。
「f(x) = a[0]*X^0+a[1]*X^1+a[2]*X^2+...」の形であり、係数は非負でK未満の数である必要がある。

解法

http://codeforces.com/contest/933/submission/35279889

まずパッと見て思うのが剰余の定理が使えそうな感じである。
今回の条件を言い換えると「f(-K)=Pが成り立つ多項式関数fを求めよ」とできる。
「P = a[0] + a[1] * (-K) + a[2] * (-K)^2 + a[3] * (-K)^3 + ...」を成立させればいい。
この形は-K進数に変換しているような感じがある。
n進数に変換する場合はnで割っていって、余りを係数として採用、商が0でないなら、商を割って続けることを繰り返せばいい。
これを少し変更して-K進数に対応していこう。（これのCalculationの項に例がある）
大体同じなのだが、余りを取った場合に余りが負になる場合がある。
この場合は-Kをもう一つ使って、商を+1,余りを+Kすることで無理矢理、余りを非負にしよう。
これを繰り返して答えればOK

ll P, K;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> P >> K;

    vector<int> ans;
    while (P) {
        ll d = P / (-K);
        ll m = P % (-K);

        if (m < 0) d++, m += K;

        P = d;
        ans.push_back(m);
    }

    int n = ans.size();
    printf("%d\n", n);
    rep(i, 0, n) {
        if (i) printf(" ");
        printf("%d", ans[i]);
    }
    printf("\n");
}