Сгенерируйте последовательность X из заданной последовательности Y так, что Yi = gcd(X1, X2,..., Xi)

Дана последовательность Y размера N , где:

Y_i = gcd(X₁, X₂, X₃, . . ., X_i ) of some sequence X. 

Задача состоит в том, чтобы найти такую последовательность X , если любая такая X возможна.

Примечание. Если X существует, для X может быть несколько возможных значений. Достаточно сгенерировать любое значение.

Примеры:

Input: N = 2, Y = [4, 2]
Output: [4, 2]
Explanation: Y₀ = gcd(X₀) = X₀ = 4. And gcd(4, 2) = 2 = Y₁.

Input: [1, 3]
Output: -1
Explanation: No such sequence can be formed.

Подход: Задача может быть решена на основе следующего наблюдения:

• i -й элемент Y = gcd(X ₁ , X ₂ , X ₃ ,..., X _i ) и (i + 1)-й элемент Y = gcd(X ₁ , X ₂ , X ₃ ,..., X _я, X _i+1 ).
• Таким образом, (i+1)-й элемент Y может быть записан как gcd(gcd(X1, X2, X3, . . ., _Xi ), _{Xi+1 ) ——-} ( ₁ ), т. е. gcd( a, b, c) = gcd( gcd(a, b), c).
• Итак, (i+1)-й элемент Y равен gcd( i-му элементу Y, X(i+1)) из уравнения 1.
• Следовательно, (i+1)-й элемент Y должен быть делителем i-го элемента Y, так как НОД двух элементов является делителем обоих элементов.
• Поскольку (i+1)-й элемент Y делит i-й элемент Y, gcd( i-й элемент, (i+1)-й элемент) всегда равен (i+1)-му элементу.

Следуйте иллюстрации ниже:

Illustration:

For example: N = 2, Y = {4, 2}

• X[0] = Y[0] = 4 because any number is GCD of itself.
• Y[1] = GCD(X[0], X[1]). Now GCD(X[0]) = Y[0]. So Y[1] = GCD(Y[0], X[1]). Therefore Y[1] should be a factor of Y[0].
• In the given example 2 is a factor of 4. So forming a sequence X is possible and X[1] can be same as Y[1]. 
  Assigning X[1] = 2 satisfies GCD (X[0, X[1]) = Y[1] = 2.
• So the final sequence X is {4, 2}.

Итак, следуйте шагам, указанным ниже, чтобы решить проблему на основе приведенного выше наблюдения:

1. Начните обход Y с начала последовательности.
2. Если в заданной последовательности Y есть какой-либо (i+1)-й элемент , который не делит i-й элемент, то последовательность X не может быть сгенерирована .
3. Если (i+1)-й элемент делит i-й элемент, то существует последовательность X и ее можно найти по приведенному выше заключению о (i+1)-м элементе Y
   является gcd( i-й элемент Y, X _i+1 ) и X _i+1 = Y _i+1 является возможным значением для X _i+1 .

Ниже приведена реализация подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(1)