GCDSUBARRAYS - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: satyam_343
Testers: IceKnight1093, tejas10p
Editorialist: IceKnight1093

DIFFICULTY:

1498

PREREQUISITES:

None

PROBLEM:

Given N and K, construct an array A of length N such that

\sum_{i=1}^N \sum_{j=i}^N \gcd(A_i, A_{i+1}, \ldots, A_j) = K

EXPLANATION:

Every subarray has a gcd of at least 1, and an array of length N has \frac{N\cdot (N+1)}{2} subarrays.
So, if K \lt \frac{N\cdot (N+1)}{2}, constructing a valid array is of course impossible.

Now, let K \geq \frac{N\cdot (N+1)}{2}. Constructing an array is always possible in this case, here’s one way.

The number which gives us the most control over the sum is 1, so it’d be nice if we could make most of the subarray gcds 1.
One easy way to do this is to form an array of the form [1, 1, 1, \ldots, 1, x] for some x \geq 1.

If you compute the subarray gcds for this array, you’ll see that except the singleton subarray [x], every other subarray has a gcd of 1.

So, the sum of subarray gcds equals x + \frac{N\cdot (N+1)}{2} - 1.
Simply choose x = K+1-\frac{N\cdot (N+1)}{2} and this sum equals K, so we’re done!

Notice that K \geq \frac{N\cdot (N+1)}{2} guarantees that x \geq 1.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
	n, k = map(int, input().split())
	if k < n*(n+1)//2: print(-1)
	else: print(*([1]*(n-1) + [k - n*(n-1)//2 - (n-1)]))
2 Likes