9090: CodeChef KSIZEGCD - Maximum of GCDs
[Creator : ]
Description
You are given an array $A$ of $N$ positive integers.
The power of a subarray $A[L,R]\ (1≤L≤R≤N)$ having size (R−L+1) is defined as gcd($A_L,A_{(L+1)},…,A_R$), where gcdgcd denotes the greatest common divisor.
Your task is to find the maximum power of a subarray of size $k$, for all $1≤k≤N$.
A subarray is formed by deleting some (possibly zero) elements from the beginning of the array and some (possibly zero) elements from the end of the array.
The power of a subarray $A[L,R]\ (1≤L≤R≤N)$ having size (R−L+1) is defined as gcd($A_L,A_{(L+1)},…,A_R$), where gcdgcd denotes the greatest common divisor.
Your task is to find the maximum power of a subarray of size $k$, for all $1≤k≤N$.
A subarray is formed by deleting some (possibly zero) elements from the beginning of the array and some (possibly zero) elements from the end of the array.
Input
The first line contains a single integer $T$: the number of test cases.
The first line of each test case contains a positive integer $N$: the size of array $A$.
The second line of each test case contains $N$ positive integers: $A_1,A_2,A_3,…,A_N$.
The first line of each test case contains a positive integer $N$: the size of array $A$.
The second line of each test case contains $N$ positive integers: $A_1,A_2,A_3,…,A_N$.
Output
For each test case, output $N$ space-separated positive integers.
The $i^{th}$ integer should be the maximum power among all subarrays of $A$ with size $i$.
The $i^{th}$ integer should be the maximum power among all subarrays of $A$ with size $i$.
Constraints
$1≤T≤10^4$
$1≤N≤10^5$
$1≤A_i≤10^9$
The sum of $N$ over all test cases won't exceed $2⋅10^5$.
$1≤N≤10^5$
$1≤A_i≤10^9$
The sum of $N$ over all test cases won't exceed $2⋅10^5$.
Sample 1 Input
5
4
5 5 5 5
4
4 2 3 1
3
6 10 15
5
2 6 3 9 24
5
3 11 7 2 5
Sample 1 Output
5 5 5 5
4 2 1 1
15 5 1
24 3 3 3 1
11 1 1 1 1
Test case 1:
- Subarray of size 1 having maximum power is [$A_2$]. Thus, gcd($A_2$)=5.
- Subarray of size 2 having maximum power is [$A_3,A_4$]. Thus, gcd($A_3,A_4$)=5.
- Subarray of size 3 having maximum power is [$A_1,A_2,A_3$]. Thus, gcd($A_1,A_2,A_3$)=5.
- Subarray of size 4 having maximum power is [$A_1,A_2,A_3,A_4$]. Thus, gcd($A_1,A_2,A_3,A_4$)=5.