Subarray Sum

general
1

Subarray Set of an array is defined as the set of sum of all elements of subarrays of the array.For example, Subarray Set of [1,2,5] is (1,2,3,5,7,8).

A is an array of positive integers having length N. The elements of the array are not known. However, it is known that the sum of all elements is S.

Find the numbers which always occur in the Subarray Set of A for any A satisfying the above constraints.

Input:

First line contains the number of test case T.
T lines follow ,each containing 2 integers N and S.

Output:

For each test case print the total no. of numbers which occur in A.In the next line print the numbers separated by spaces in increasing order.

Constraints_:

1<=T<=10

1<=N<=10^5

1<=S<=10^5

Sample Input:

2

3 5

5 6

Sample Output:

3

1 3 5

6

1 2 3 4 5 6

2

is there some other good solution other than FFT?

3

for values > N only S will always occur in subarray set of A

To avoid a value S - X > N, take S-N then X-1 1’s then 2 then rest all 1’s
for X = 4, take this S-N 1 1 1 2 1 1 1 1, this can never make S - 4.

Now for values X <= N, it can be avioded in an array to occur if S >= X * (N/X) + N. (N/X is integer division)
Try to build array for this condition

all left values will always occur in the subarray set of A (havent proved yet).

4

Its correct and can be proved using pigeonhole principle.

5

oops, I misread the problem, I thought A is given.