Accounting Numeral System

시간 제한1초메모리 제한1024 MB

요약
주어진 n을 이항계수의 합 C(x_m, m) + ... + C(x_1, 1) 꼴로 나타내고, 조건 0 ≤ x_1 < ... < x_m을 만족하는 x_i들을 출력한다.
난이도

보통10점 중 7점

유형
수학, 조합론, 그리디, 이분 탐색
정답자
아직 제출이 없습니다

문제

The latest Accounting Numeral System is the top accounting system in the whole world. Its creator, Dr. Ceizenpok, is the best expert of the respective authority. Any positive integer nn in this system based mm is represented as a sum of mm parts:

n=C_x_mm+C_x_m−1m−1+C_x_m−2m−2+…+C_x_11,n = C\_{x\_m}^m + C\_{x\_{m-1}}^{m-1} + C\_{x\_{m-2}}^{m-2} + \ldots + C\_{x\_1}^1,

while x_1,x_2,…,x_mx\_1, x\_2, \ldots , x\_m --- are such integers that 0≤x_1<x_2<…<x_m0 \le x\_1 < x\_2 < \ldots < x\_m. Numbers C_km=k!m!,(k−m)!C\_k^m = \frac{k!}{m!\\,(k-m)!} our experts call accounting indexes. Each number nn in this system is recorded as n=(x_m)…(x_2)(x_1)‾n = \overline{(x\_m) \ldots (x\_2)(x\_1)}, and it is considered that 0!=10! = 1 and C_km=0C\_k^m = 0, if m>km > k. For example, number 99 in the accounting system based 33 is recorded as ({\bfseries 4})({\bfseries 3})({\bfseries 2}), because 9=C_43+C_32+C_219 = C\_{\mathbf 4}^3 + C\_{\mathbf 3}^2 + C\_{\mathbf 2}^1, and number 11 in this system based 22 looks like:({\bfseries 2})({\bfseries 0}), because 1=C_22+C_011 = C\_{\mathbf 2}^2 + C\_{\mathbf 0}^1.

You have to find a representation of an integer nn in the accounting numeral system based mm.

입력

Single line contains two integers nn and mm (1≤n≤10161 \le n \le 10^{16}, 2≤m≤1,0002 \le m \le 1\\,000).

출력

Single line should contain a sequence of mm space-separated integers x_m,…,x_2,x_1x\_m, \ldots, x\_2, x\_1, that form a number designation nn in the accounting numeral system. Number x_mx\_m is the leftmost digit in the number designation nn, and x_1x\_1 --- its rightmost one.

예제2

  1. 예제 1

    입력
    9 3
    
    예상 출력
    4 3 2
    
  2. 예제 2

    입력
    5 2
    
    예상 출력
    3 2