1497C2.md (1166B)
1 Source: https://codeforces.com/problemset/problem/1497/C2 2 3 C2. k-LCM (hard version) 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 It is the hard version of the problem. The only difference is that in this version $3 \le k \le n$. 22 23 You are given a positive integer $n$. Find $k$ positive integers $a_1, a_2, \ldots, a_k$, such that: 24 25 * $a_1 + a_2 + \ldots + a_k = n$ 26 * $LCM(a_1, a_2, \ldots, a_k) \le \frac{n}{2}$ 27 28 Here $LCM$ is the [least common multiple](https://en.wikipedia.org/wiki/Least_common_multiple) of numbers $a_1, a_2, \ldots, a_k$. 29 30 We can show that for given constraints the answer always exists. 31 32 Input 33 34 The first line contains a single integer $t$ $(1 \le t \le 10^4)$ — the number of test cases. 35 36 The only line of each test case contains two integers $n$, $k$ ($3 \le n \le 10^9$, $3 \le k \le n$). 37 38 It is guaranteed that the sum of $k$ over all test cases does not exceed $10^5$. 39 40 Output 41 42 For each test case print $k$ positive integers $a_1, a_2, \ldots, a_k$, for which all conditions are satisfied. 43 44 Example 45 46 Input 47 48 ``` 49 2 50 6 4 51 9 5 52 ``` 53 54 Output 55 56 ``` 57 1 2 2 1 58 1 3 3 1 1 59 ```