Problem Link
Author: Evgeniy Artemov
Editorialist: Rishabh Dhiman
Problem
Find an integer sequnce A of length n such that
- gcd(A_i, A_{i + 1 \mod n}) > 1
- gcd(A_i, A_{i + 1 \mod n}, A_{i + 2 \mod n}) = 1
for all 0 \le i \le n - 1.
Constraints:
A_i < 10^9
1 \le \text{test cases} \le 10^3
Subtask 1: 1 \le N \le 3,333
Subtask 2: 1 \le N \le 50,000
Prerequisites
Sieve of Eratosthenes, previous experience with \gcd
Super Quick Solution
\gcd and construction problem, so work with primes, if p_n is the n-th prime, this simple sequence would work, \{p_1p_n, p_1p_2, p_2p_3, \dots, p_{n - 1}p_n\}, this would work for subtask 1 but p_{n - 1}p_n > 10^9 for n = 50,000.
Playing around a bit you get the following sequence that works,
- A_0 = 35 = p_3p_4
- A_1 = 15 = p_2p_3
- A_{4i} = p_1p_{2i + 4}
- A_{4i + 1} = p_2p_{2i + 4}
- A_{4i + 2} = p_2p_{2i + 5}
- A_{4i + 3} = p_1p_{2i + 5}
- A_{n - 1} \to p_4A_{n - 1}
Explanation
Since, there isn’t much to explain in the way of a solution, I’ll just explain how I came up with such a sequence.
So, the thing with \gcd is that it acts pretty unpredictabily in most circumstances, unless we are dealing with primes. So, a good idea would be to deal with primes and that’s exactly what we do!
Let us ignore the condition, that A_i < 10^9 for a while.
Also, assume all the indices are modulo n.
So, what we would like is that \gcd(A_i, A_{i + 1}) = \text{a prime}, \gcd(A_{i + 1}, A_{i + 2}) = \text{another unrelated prime}. Since, this would imply
since \text{a prime} doesn’t divide A_{i + 2}.
Keeping this in mind, we can come up with the very simple solution \{p_1p_n, p_1p_2, \dots \}.
However, this approach does have a drawback, the numbers would be too large in subtask 2.
Let us call our initial solution S.
One thing, we can notice about S is that it is an overkill solution.
What I mean is that rather than having \gcd(S_{i}, S_{i + 1}, S_{i + 2}) = 1, we have \gcd(S_x, S_y, S_z) = 1 for all x, y, z.
This indicates that we can instead repeat some primes, ie, rather than using a new prime for each S_i, we can recycle one.
If we consider the \gcd of two consecutive elements, and force an alternating cycle as such,
we’d be done. You can try a few cases to see that this isn’t really very feasible.
But what if we do it as such,
we see that yeah, this actually works!
But there’s a small problem, though, it occurs when we are dealing with n - 1, n, 1 and n, 1, 2. So, what can we do to remove, this? Just make sure that the first two elements aren’t divisible by 2, but we still need some primes to link the first two elements. This is actually pretty simple if we use 5 and 7 here.
Implementation
Just use classical Sieve of Eratosthenes to generate the first 25003 primes, because those are all we need.
Also, there’s a faster way to write the 4 cases of A_{4i}, A_{4i + 1}, A_{4i + 2} and A_{4i + 3},