[Solved] Maximum of GCDs January Long 2023 CodeChef

Maximum of GCDs: 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(AL​,A(L+1)​,…,AR​), where gcd⁡ 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.

Note the unusual time limit in this problem.

Input Format

• 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: A1​,A2​,A3​,…,AN​.

Output Format

For each test case, output N space-separated positive integers.
The ith integer should be the maximum power among all subarrays of A with size i.

Constraints

• 1≤T≤10^4
• 1≤N≤10^5
• 1≤Ai​≤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

Input:

5 5 5 5
4 2 1 1
15 5 1
24 3 3 3 1
11 1 1 1 1

Explanation:

Test case 11:

• Subarray of size 11 having maximum power is [A2​]. Thus, gcd(A2​)=5.
• Subarray of size 22 having maximum power is [A3​,A4​]. Thus, gcd(A3​,A4​)=5.
• Subarray of size 33 having maximum power is [A1​,A2​,A3​]. Thus, gcd(A1​,A2​,A3​)=5.
• Subarray of size 44 having maximum power is [A1​,A2​,A3​,A4​]. Thus, gcd(A1​,A2​,A3​,A4​)=5.

Test case 22:

• Subarray of size 11 having maximum power is [A1​]. Thus, gcd(A1​)=4.
• Subarray of size 22 having maximum power is [A1​,A2​]. Thus, gcd(A1​,A2​)=2.
• Subarray of size 33 having maximum power is [A1​,A2​,A3​]. Thus, gcd(A1​,A2​,A3​)=1.
• Subarray of size 44 having maximum power is [A1​,A2​,A3​,A4​]. Thus, gcd(A1​,A2​,A3​,A4​)=1.

Test case 33:

• Subarray of size 11 having maximum power is [A3​]. Thus, gcd(A3​)=15.
• Subarray of size 22 having maximum power is [A2​,A3​]. Thus, gcd(A2​,A3​)=5.
• Subarray of size 33 having maximum power is [A1​,A2​,A3​]. Thus, gcd(A1​,A2​,A3​)=1.

Note that there can be multiple subarrays with the same power.

Solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
#define pb push_back
#define ff first
#define ss second
const int N=2e3+7;
const int mod=1e9+7;
const double eps=1e-9;
const double pi=    3.14159265358979323846;
using namespace std;  
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
             tree_order_statistics_node_update>
    op_set;

int32_t main() 
{
   ios_base::sync_with_stdio(false);
   cin.tie(0);

   int t;
   cin >> t;
   while(t--)
   {
        int n;
        cin >> n;

        vector<int> ans(n,0);
        map<int,int> mp;
        for(int i=0;i<n;i++)
        {
            int ex;
            cin >> ex;
            map<int,int> gmp;
            gmp[ex]=i;
            for(auto &[val,left] :mp)
            {
                int nval=__gcd(val,ex);
                if(gmp.find(nval)==gmp.end())
                    gmp[nval]=left;
                else
                    gmp[nval]=std::min(gmp[nval],left);
            }

            for(auto &[val,left] : gmp)
                ans[i-left]=std::max(ans[i-left],val);
            swap(gmp,mp);
        }

        for(int i=n-2;i>=0;i--)
            ans[i]=std::max(ans[i],ans[i+1]);

        for(auto ele : ans)
            cout << ele << " ";
        cout << "\n";
   }
}

Happy Learning – If you require any further information, feel free to contact me.