Title Link: Array Stabilization (GCD version)

General meaning

Given an array of length n, the subscripts are from 1 to n. where an and a1 are connected (form a ring)

Each round of operation yields a new array b: for all I ∈ [1, n], b[i] = gcd(a[i], a[i + 1]) (b[n] = gcd(a[n], a[1]) Finally, copy the new array b to the original array a

Q: after how many rounds of operation, all the numbers in the a array are the same

Problem solving ideas

Considering the final a array, there are many possibilities for equality This is not convenient for our next thinking

Taking gcd from two numbers is equivalent to retaining the common prime factor of two numbers After performing numerous gcd operations on the whole sequence, it is equivalent that each number in the sequence becomes the product of all common prime factors in the original sequence Therefore, we might as well implement a[] /= gcd(a []) At this point, the final sequence we get must be the full 1 sequence

Now our purpose is very clear: find how many operations are performed so that each number in the sequence is equal to 1

Considering that it is the number of position I every time (assuming a [i]! = 1), gcd operation is performed with the number of position i+1. If the two numbers are mutually prime, one operation can make the number of position I become 1

If it is not coprime, it may be assumed that there is a common factor 2. After this round of change, a[i] = 2, a[i+1] needs to be determined according to a[i+2], and the situation of a[i+2] needs to be considered according to... We consider the results after a round of operation of a[i+1]:
Situation ①: if factor 2 is not contained in a[i+1] after operation, it indicates that factor 2 is not contained in a[i+2]. At this time, two rounds of operation can change a[i] to 1
Case ②: if there is a factor 2 in a[i+1] after the operation, it indicates that there is also a factor 2 in a[i+2]. At this time, we need to assume the case of a[i+2], which is the same as that of a[i+1]

We can find that if a[i], a[i + 1],..., a[i + k] all have common factor 2, and a [K + 1] does not have factor 2, we need K rounds of operation to change a[i] to 1

It is concluded that for each position I, we start to take gcd continuously. When gcd(a[i], a[i + 1],..., a[i + k]) == 1 for the first time, it means that the position I needs to operate the K wheel to become 1

So for this question, we take max of k in all positions as the final answer

How do we get the k of each position? Segment tree + two points outside the tree DS players can only think of violent segment tree

We use the segment tree to maintain the static gcd information of each interval For each location, query the location with gcd == 1 on the left

Here is a little detail: since a[n] is followed by a[1], the array in the title is a ring. We can simulate the ring by copying the array again Namely: a[n + 1] = a[1], a[n + 2] = a[2],..., a[n + n] = a[n]

AC code

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
typedef long long ll;
const int N = 4E5 + 10; //Remember to drive twice
int a[N];
struct node {
	int l, r;
	int val;
}t[N << 2];
void pushup(int x) { t[x].val = gcd(t[x << 1].val, t[x << 1 | 1].val); }
void build(int l, int r, int x = 1) {
	t[x] = { l, r, a[l] };
	if (l == r) return;
	int mid = l + r >> 1;
	build(l, mid, x << 1), build(mid + 1, r, x << 1 | 1);
	pushup(x);
}
int ask(int l, int r, int x = 1) { //gcd of query [l, r]
	if (l <= t[x].l and r >= t[x].r) return t[x].val;
	int mid = t[x].l + t[x].r >> 1;
	int res = 0;
	if (l <= mid) res = ask(l, r, x << 1);
	if (r > mid) res = gcd(res, ask(l, r, x << 1 | 1));
	return res;
}
int main()
{
	int t; cin >> t;
	while (t--) {
		int n; scanf("%d", &n);

		int d = 0; //gcd(a []) is obtained
		rep(i, n) scanf("%d", &a[i]), d = gcd(d, a[i]);
		if (d != 1) rep(i, n) a[i] /= d;

		rep(i, n) a[n + i] = a[i];
		n <<= 1;

		build(1, n);

		int res = 0;
		rep(i, n / 2) {
			if (a[i] == 1) continue;

			int l = i + 1, r = n; //Value range of right endpoint
			while (l < r) {
				int mid = l + r >> 1;
				int cou = ask(i, mid);
				if (cou == 1) r = mid;
				else l = mid + 1;
			}
			res = max(res, r - i);
		}

		printf("%d\n", res);
	}

	return 0;
}

END