| Codeforces Round 462 (Div. 1) |
|---|
| Закончено |
Чтобы выкинуть старые вещи и встретить чистый новый год, в доме обязательно нужно сделать генеральную уборку.
Маленький Томми нашел старый многочлен и почистил его, заменив его остатком от деления на другой многочлен. Теперь он уже пожалел об этом...
По двум данным целым числам p и k найдите многочлен f(x) с неотрицательными целочисленными коэффициентами, строго меньшими k, такой, что его остаток от деления на (x + k) равен p. Иными словами, f(x) = q(x)·(x + k) + p, где q(x) — многочлен (не обязательно с целочисленными коэффициентами).
Единственная строка содержит два целых числа p и k (1 ≤ p ≤ 1018, 2 ≤ k ≤ 2 000).
Если подходящего многочлена не существует, выведите -1. Иначе выведите две строки.
В первую строку выведите целое число d — количество коэффициентов в многочлене.
Во вторую строку выведите d целых чисел a0, a1, ..., ad - 1, которые описывают многочлен 
, удовлетворяющий всем условиям. Должно выполняться 0 ≤ ai < k для всех 0 ≤ i ≤ d - 1, а также ad - 1 ≠ 0.
Если существует несколько ответов, выведите любой.
46 2
7
0 1 0 0 1 1 1
2018 214
3
92 205 1
В первом примере f(x) = x6 + x5 + x4 + x = (x5 - x4 + 3x3 - 6x2 + 12x - 23)·(x + 2) + 46.
Во втором примере f(x) = x2 + 205x + 92 = (x - 9)·(x + 214) + 2018.
