KSIZEGCD - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: nicholask
Testers: iceknight1093, tabr
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Computing all subarray GCDs

PROBLEM:

You are given an array A. For each K from 1 to N, compute the maximum GCD of a subarray of length K.

EXPLANATION:

There are \mathcal{O}(N^2) subarrays, and while going through them all is impossible, it’s actually possible to compute all their GCDs in a compressed form.

The main observation that allows this to happen is the fact that there are only \mathcal{O}(N\log\max A) distinct subarray GCDs.

Proof

For convenience, let f(i, j) = \gcd(A_i, A_{i+1}, \ldots, A_j).

Let’s fix an index R (1 \leq R \leq N), and look at all subarrays of the form [i, R] for 1 \leq i \leq R.

Suppose you knew f(i, R). What’s its relation with f(i-1, R)?
We know that f(i-1, R) = \gcd(f(i, R), A_{i-1}).
In particular, f(i-1, R) will always be a divisor of f(i, R).

So, we either have f(i-1, R) = f(i, R) (which doesn’t increase the number of distinct GCDs), or f(i-1, R) is a strictly smaller factor of f(i, R), in which case f(i-1, R) \leq f(i, R)/2.
This halving can only happen \log{A_R} times before the GCD reaches 1 and never changes again.

So, there are \log A_R distinct values of f(i, R).
Summing this across all R gives us an upper bound of N\log\max A distinct subarray GCDs.

Computing them all isn’t too hard; in fact, the proof above gives us a pretty reasonable way to compute them all quickly.

How?

Notice that the GCDs ending at a given index form continuous segments, so its enough to find the endpoints of these segments: that will give us information about every subarray.

Let’s define dp(i, x) to be the length of the longest subarray ending at i with gcd x.
We only need to care about those pairs (i, x) for which this value is non-zero, and the earlier discussion tells us that there are \leq N\log\max A such states.

Computing all these values isn’t too hard either: notice that a subarray ending at i can be obtained by extending a subarray ending at i-1, so:

dp(i, x) = 1 + \max_y(dp(i-1, y))

across all y such that \gcd(y, A_i) = x.

There are only \mathcal{O}(\log) non-zero values of y, so simply store them all and iterate across them, each time taking its GCD with x and updating the correct dp value.

The method is also described in short in point 3 of this blog post, with code.

At any rate, now that we know all subarray GCDs, the problem is almost solved.

Let \text{ans}_i be the answer for the subarrays of length i.
Then, using what we computed earlier:

  • Let L be the length of the longest subarray ending at i with GCD g.
  • Then, set \text{ans}_L = \max(\text{ans}_L, g).

Finally, set \text{ans}_i = \max(\text{ans}_i, \text{ans}_{i+1}, \ldots, \text{ans}_N); which can be done in \mathcal{O}(N) by taking suffix maximums of the \text{ans} array.

As an aside, we make \mathcal{O}(N\log\max A) GCD calls, each of which is technically \mathcal{O}(\log\max A) itself.
This gives us an upper bound of \mathcal{O}(N\log^2(\max A)) for the time complexity.
However, it’s likely a bit faster in practice as mentioned here and here; the analysis is a bit harder but I wouldn’t be surprised if it’s \mathcal{O}(N\log\max A + \log\max A).

TIME COMPLEXITY:

\mathcal{O}(N\log^2 (\max A)) per testcase, likely faster in practice.

CODE:

Setter's code (C++)
#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
	while (b) b^=a^=b^=a%=b;
	return a;
}
void solve(){
	int n;
	cin>>n;
	int a[n+1];
	for (int i=1; i<=n; i++) cin>>a[i];
	int ans[n+1];
	for (int i=1; i<=n; i++) ans[i]=0;
	vector <pair <int,int> > f;
	for (int i=1; i<=n; i++){
		for (pair <int,int>&j: f) j.first=gcd(j.first,a[i]);
		f.push_back(make_pair(a[i],i));
		vector <pair <int,int> > cur;
		for (pair <int,int> j: f){
			if (cur.empty()||cur.back().first!=j.first) cur.push_back(j);
		}
		f.swap(cur);
		for (pair <int,int> j: f) ans[i-j.second+1]=max(ans[i-j.second+1],j.first);
	}
	for (int i=n-1; i>0; i--) ans[i]=max(ans[i],ans[i+1]);
	for (int i=1; i<=n; i++) cout<<ans[i]<<" \n"[i==n];
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t;
	cin>>t;
	while (t--) solve();
}
Tester's code (C++)
// not WA, sry
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

struct input_checker {
    string buffer;
    int pos;

    const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
    const string number = "0123456789";
    const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    const string lower = "abcdefghijklmnopqrstuvwxyz";

    input_checker() {
        pos = 0;
        while (true) {
            int c = cin.get();
            if (c == -1) {
                break;
            }
            buffer.push_back((char) c);
        }
    }

    int nextDelimiter() {
        int now = pos;
        while (now < (int) buffer.size() && buffer[now] != ' ' && buffer[now] != '\n') {
            now++;
        }
        return now;
    }

    string readOne() {
        assert(pos < (int) buffer.size());
        int nxt = nextDelimiter();
        string res;
        while (pos < nxt) {
            res += buffer[pos];
            pos++;
        }
        return res;
    }

    string readString(int minl, int maxl, const string& pattern = "") {
        assert(minl <= maxl);
        string res = readOne();
        assert(minl <= (int) res.size());
        assert((int) res.size() <= maxl);
        for (int i = 0; i < (int) res.size(); i++) {
            assert(pattern.empty() || pattern.find(res[i]) != string::npos);
        }
        return res;
    }

    int readInt(int minv, int maxv) {
        assert(minv <= maxv);
        int res = stoi(readOne());
        assert(minv <= res);
        assert(res <= maxv);
        return res;
    }

    long long readLong(long long minv, long long maxv) {
        assert(minv <= maxv);
        long long res = stoll(readOne());
        assert(minv <= res);
        assert(res <= maxv);
        return res;
    }

    void readSpace() {
        assert((int) buffer.size() > pos);
        assert(buffer[pos] == ' ');
        pos++;
    }

    void readEoln() {
        assert((int) buffer.size() > pos);
        assert(buffer[pos] == '\n');
        pos++;
    }

    void readEof() {
        assert((int) buffer.size() == pos);
    }
};

struct sparse {
    using T = int;
    int n;
    int h;
    vector<vector<T>> table;

    T op(T x, T y) {
        return __gcd(x, y);
    }

    sparse(const vector<T>& v) {
        n = (int) v.size();
        h = 32 - __builtin_clz(n);
        table.resize(h);
        table[0] = v;
        for (int j = 1; j < h; j++) {
            table[j].resize(n - (1 << j) + 1);
            for (int i = 0; i <= n - (1 << j); i++) {
                table[j][i] = op(table[j - 1][i], table[j - 1][i + (1 << (j - 1))]);
            }
        }
    }

    T get(int l, int r) {
        assert(0 <= l && l < r && r <= n);
        int k = 31 - __builtin_clz(r - l);
        return op(table[k][l], table[k][r - (1 << k)]);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    input_checker in;
    int tt = in.readInt(1, 1e4);
    in.readEoln();
    int sn = 0;
    while (tt--) {
        int n = in.readInt(1, 1e5);
        sn += n;
        in.readEoln();
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            a[i] = in.readInt(1, 1e9);
            (i == n - 1 ? in.readEoln() : in.readSpace());
        }
        sparse sp(a);
        vector<int> ans(n);
        for (int i = 0; i < n; i++) {
            function<void(int, int, int, int)> Check = [&](int low, int high, int lv, int hv) {
                if (low + 1 >= high) {
                    return;
                }
                if (lv == hv) {
                    return;
                }
                if (ans[high - i] > lv) {
                    return;
                }
                int mid = (high + low) >> 1;
                int mv = sp.get(i, mid + 1);
                ans[mid - i] = max(ans[mid - i], mv);
                Check(low, mid, lv, mv);
                Check(mid, high, mv, hv);
            };
            ans[0] = max(ans[0], a[i]);
            ans[n - 1 - i] = max(ans[n - 1 - i], sp.get(i, n));
            Check(i, n - 1, a[i], sp.get(i, n));
        }
        for (int i = 0; i < n; i++) {
            cout << ans[i] << " \n"[i == n - 1];
        }
    }
    assert(sn <= 2e5);
    in.readEof();
    cerr << sn << endl;
    return 0;
}
Editorialist's code (Python)
import sys
input = sys.stdin.readline
from math import gcd

for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = [0]*(n+1)
	gcds = {}
	sm = 0
	for x in a:
		new_gcds = {x:1}
		for g in gcds.keys():
			G = gcd(x, g)
			if G not in new_gcds: new_gcds[G] = gcds[g]+1
			else: new_gcds[G] = max(new_gcds[G], gcds[g]+1)
		gcds = new_gcds
		for g in gcds.keys():
			ans[gcds[g]] = max(ans[gcds[g]], g)
	for i in reversed(range(1, n)):
		ans[i] = max(ans[i], ans[i+1])
	print(*ans[1:])
1 Like

Is there any simpler solution?

I got WA, i thought like …gcd only decrease after any two consecutive element In array…

So i took gcd of all subarray of size two …

1 Like

I use a segment tree to compute the maximum right point r of the subarray starting from l with gcd(A_l,...,A_r)=x. This could be done with binary search on segment tree. And, starting from each r, you can do the next round of binary search to find out next subarray with smaller gcd. This will happen only logA_l times for each l. So the total time complexity is O(Nlog^2maxA).

1 Like