Array Transformation with GCD
Given an array A of N positive integers, transform it into an array where each element A[i] is replaced by the greatest common divisor (GCD) of A[i] and all preceding elements (A[0] through A[i-1]). For the first element A[0], it remains unchanged. Print the transformed array.
Input
The first line contains an integer N. The second line contains N space-separated positive integers representing the array A.
Output
Print N space-separated positive integers, the elements of the transformed array.
Constraints
1 <= N <= 200000 1 <= A[i] <= 10^9
Example 1
5 12 6 18 4 10
12 6 6 2 2
transformed_A[0]=12. transformed_A[1]=gcd(6, 12)=6. transformed_A[2]=gcd(18, gcd(12,6))=gcd(18,6)=6. transformed_A[3]=gcd(4, gcd(12,6,18))=gcd(4,6)=2. transformed_A[4]=gcd(10, gcd(12,6,18,4))=gcd(10,2)=2.
Example 2
3 7 7 7
7 7 7
All elements are the same, GCDs remain 7 until the element itself divides the prefix GCD.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 12 6 18 4 10
3 7 7 7