PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
You’re given integers N and K.
Find any array A of length N, containing distinct integers between 1 and 10^9, such that
EXPLANATION:
First, note that the gcd of two positive integers is \geq 1, so the value \sum_{i=1}^{N-1} \gcd(A_i, A_{i+1}) is definitely at least N-1.
So, if K \lt N-1 no solution exists.
We’re now left with K \geq N-1.
Let’s solve K = N-1 in particular.
For this to be the case, every adjacent GCD should be equal to 1.
There are several ways to achieve this while ensuring that elements are distinct; perhaps the simplest is to note that \gcd(x, x+1) = 1 for any x, so if we can ensure that adjacent elements differ by 1 their GCD will definitely equal 1.
This leads to a simple construction: [1, 2, 3, \ldots, N].
Now, consider K \gt N-1.
We already know how to obtain GCDs that equal 1.
Let’s now try to make exactly one GCD larger than 1.
So, suppose we make \gcd(A_1, A_2) = g, while all other adjacent GCDs equal 1.
Then, the overall sum will equal g + (N-2).
For this to equal K, we must have g = K - (N-2).
One way to achieve this is as follows:
- Let g = K - (N-2).
- Set A_1 = g and A_2 = 2g.
This guarantees that \gcd(A_1, A_2) = \gcd(g, 2g) = g. - Then, use consecutive numbers for the remaining elements.
When doing so, we need to ensure that elements are distinct (so neither g nor 2g get used again), and also that \gcd(2g, A_3) = 1. - A simple way to do this is to choose A_3 = 2g+1 and go from there, so that the array looks like
[g, 2g, 2g+1, 2g+2, \ldots, 2g+N-2]
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n, k = map(int, input().split())
if k < n-1: print(-1)
else:
k -= n - 2
ans = [k, 2*k] + list(range(2*k + 1, 2*k + n - 1))
print(*ans)
