k-LCM (hard version) (Codeforces 1497C2)
Tags: Math, constructive algorithms

It is the hard version of the problem. The only difference is that in this version $$$3 \le k \le n$$$.You are given a positive integer $$$n$$$. Find $$$k$$$ positive integers $$$a_1, a_2, \ldots, a_k$$$, such that:  $$$a_1 + a_2 + \ldots + a_k = n$$$  $$$LCM(a_1, a_2, \ldots, a_k) \le \frac{n}{2}$$$ Here $$$LCM$$$ is the least common multiple of numbers $$$a_1, a_2, \ldots, a_k$$$.We can show that for given constraints the answer always exists.

Input: The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10^4)$$$  — the number of test cases.The only line of each test case contains two integers $$$n$$$, $$$k$$$ ($$$3 \le n \le 10^9$$$, $$$3 \le k \le n$$$).It is guaranteed that the sum of $$$k$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case print $$$k$$$ positive integers $$$a_1, a_2, \ldots, a_k$$$, for which all conditions are satisfied.


Sample Inputs:
2
6 4
9 5

Sample Outputs:
1 2 2 1 
1 3 3 1 1

Solution (Python):
from sys import stdin, stdout

def get_ints():
    return map(int, stdin.readline().split())

def PRINT(s):
    stdout.write(s + '\n')
for w in range(int(stdin.readline())):
    (n, k) = get_ints()
    n -= k - 3
    x = 1
    a = n
    while a % 2 == 0:
        x *= 2
        a = a // 2
    if a == 1:
        s = ' '.join([str(a) for a in [x // 2, x // 4, x // 4]])
    else:
        s = ' '.join([str(a) for a in [x, x * (a - 1) // 2, x * (a - 1) // 2]])
    PRINT(s + ' 1' * (k - 3))

Solution (Python):
Test = int(input())
Ans = ''

def solve(n, k):
    ans = '1 ' * (k - 3)
    n = n - (k - 3)
    if n % 3 == 0:
        return ans + str(n // 3) + ' ' + str(n // 3) + ' ' + str(n // 3) + '\n'
    if n & n - 1 == 0:
        return ans + str(n // 2) + ' ' + str(n // 4) + ' ' + str(n // 4) + '\n'
    if n % 2 != 0:
        return ans + str(n // 2) + ' ' + str(n // 2) + ' 1\n'
    bound = n // 2
    if bound % 2 == 0:
        return ans + str(n // 2) + ' ' + str(n // 4) + ' ' + str(n // 4) + '\n'
    return ans + str(bound - 1) + ' ' + str(bound - 1) + ' ' + str(n - 2 * (bound - 1)) + '\n'
for i in range(Test):
    (n, k) = [int(i) for i in input().split()]
    Ans = Ans + solve(n, k)
print(Ans)

Solution (Python):
for _ in range(int(input())):
    (n, k) = map(int, input().split())
    n -= k - 3
    if n & 1:
        print('1 ' * (k - 2) + str(n >> 1), n >> 1)
    elif not n & 3:
        print('1 ' * (k - 3) + str(n >> 1), n >> 2, n >> 2)
    else:
        print('1 ' * (k - 3) + '2', (n >> 1) - 1, (n >> 1) - 1)