Expert.
Put your skills to the test.

Problem summary

For a positive integer vector A, maximize segment length times the gcd of the segment. Implement the grader function max_segment.

Constraints

1 ≤ N ≤ 3000000; 1 ≤ A[i] ≤ 2000000000.

Worked example

Official statement example.

7
6 5 10 15 2 4 8

15

Solution analysis

1. Fix a right endpoint. As the left endpoint moves left, suffix gcd values form a divisibility chain. Whenever the value changes it decreases by at least a factor of two, so at most 31 distinct positive gcd values occur.
2. Store pairs (gcd, earliest left endpoint) for the previous right endpoint. Extending by x replaces each gcd g by gcd(g,x); add the singleton suffix as well, and merge adjacent equal gcds, retaining the earliest start. For each resulting pair evaluate gcd times its longest available length.
3. For 6,5,10,15 the suffix gcd 5 at right endpoint 4 reaches left endpoint 2, giving 5×3=15. Keeping only the earliest start for gcd 5 is safe: shorter suffixes with the same gcd cannot improve that product.

Why it works

Inductively the compressed list represents every distinct suffix gcd with its earliest start: extension transforms all old suffixes exactly and the singleton covers the only new suffix. Equal values are contiguous in the divisibility chain and retaining their earliest start maximizes length. Every segment is a suffix at its right endpoint, so evaluating all stored products finds the global maximum.

Watch out. Use 64-bit products. This is a grader task: include segment.h and omit main.

Compile with the official segment.h and grader. The displayed example uses the local grader convention N followed by A.

// Key idea: Inductively the compressed list represents every distinct suffix gcd with its earliest
// start: extension transforms all old suffixes exactly and the singleton covers the only new suffix.
// Equal values are contiguous in the divisibility chain and retaining their earliest start maximizes
// length.
#include"segment.h"
#include<algorithm>
#include<numeric>
#include<utility>
#include<vector>
long long max_segment(std::vector<int>A){
    std::vector<std::pair<int,int>>previous,current;
    previous.reserve(32);
    current.reserve(32);
    long long answer=0;
    for(int right=0;right<static_cast<int>(A.size());++right){
        current.clear();
        current.push_back({A[right],right});
        for(auto[value,left]:previous){
            int g=std::gcd(value,A[right]);
            if(current.back().first==g){
                current.back().second=std::min(current.back().second,left);
            }
            else{
                current.push_back({g,left});
            }
        }
        for(auto[g,left]:current){
            answer=std::max(answer,1LL*g*(right-left+1));
        }
        previous.swap(current);
    }
    return answer;
}