题解：CF1547F Array Stabilization (GCD version)

· · 题解

解法比较抽象，但貌似比较快。
首先我们知道求 \gcd 就是对两个数所有质因数的指数求最小值，那么最后操作得到的元素一定是所有质因数最小指数次幂的积。
有点抽象，所以我举个例子 12 是由 3 的一次方和 2 的平方乘积得到的，16 是由 2 的三次方得到的，所以二者的 \gcd 就是 2 的平方。
明白了这些，那么我们就有一个想法了，可以先将所有数扫一遍，求出每个质因子的最小指数，那么答案就是非最小指数到最小指数的距离。
因为 10^6 以内的质数很多，所以我们求的时候不能一个一个指数的枚举。但我们发现 10^6 以内的数的质因子个数很少，为常数级别。所以我们求最大距离的时候只需要枚举位置，并对当前位置的数含有的质因子操作即可。

时间复杂度瓶颈在求质因数的最小指数，时间复杂度近似 O(n \sqrt{a_{max}})。完美通过。

code
#include<bits/stdc++.h>
#define aa a[i]
using namespace std;
const int N = 2e5 + 5, U = 1e6 + 5;
int n, a[N], p[N << 1], mn[N << 1], ans, cnt[N << 1];
bool book[U], book2[U], book3[U];
vector<int> mem;
struct node { int x, y; };
vector<node> num[N], lst;
inline void init() {
    for(int i = 2; i < U; ++i) {
        if(!book[i]) p[++p[0]] = i;
        for(int j = 1; j <= p[0]; ++j) {
            if(1ll * p[j] * i >= U) break;
            if(book[p[j] * i]) break;
            book[p[j] * i] = 1;
        }
    }
}
int main() {
    init();
    int t;
    scanf("%d", &t);
    while(t--) {
        ans = 0;
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i) {
            scanf("%d", a + i);
            num[i].clear();
            for(int j = 1; j <= p[0] && 1ll * p[j] * p[j] <= a[i]; ++j) {
                int cnt1 = 0;
                while(!(aa % p[j])) ++cnt1, aa /= p[j];
                if(cnt1) {
                    ++cnt[j], mem.push_back(j), mn[j] = mn[j] ? min(mn[j], cnt1) : cnt1;
                    num[i].push_back({j, cnt1});
                }
            }
            if(aa ^ 1) {
                int now = lower_bound(p + 1, p + p[0] + 1, aa) - p;
                mem.push_back(now);
                mn[now] = mn[now] ? min(mn[now], 1) : 1, ++cnt[now];
                num[i].push_back({now, 1});
            }
        }
        sort(mem.begin(), mem.end());
        unique(mem.begin(), mem.end());
        for(int i = mem.size() - 1; ~i; --i) {
            int now = mem[i];
            if(cnt[now] ^ n) mn[now] = 0, cnt[now] = 0;
        }
        for(int i = 1; i <= (n << 1); ++i) {
            int ii = i % n;
            ii = ii ? ii : n;
            for(int j = num[ii].size() - 1; ~j; --j) {
                node now = num[ii][j];
                if(now.y ^ mn[now.x]) book2[now.x] = 1;
            }
            vector<node> mm;
            while(!lst.empty()) {
                node now = lst.back();
                lst.pop_back();
                if(!book2[now.x]) {
                    ans = max(ans, i - now.y);
                }
                else book3[now.x] = 1, mm.push_back(now);
            }
            for(int j = num[ii].size() - 1; ~j; --j) {
                node now = num[ii][j];
                if(!book3[now.x] && book2[now.x]) mm.push_back({now.x, i});
            }
            for(int i = mm.size() - 1; ~i; --i) {
                int now = mm[i].x;
                book2[now] = book3[now] = 0;
            }
            while(!mm.empty()) lst.push_back(mm.back()), mm.pop_back();
        }
        printf("%d\n", ans);
        while(!mem.empty()) {
            int now = mem.back();
            mn[now] = cnt[now] = 0;
            mem.pop_back();
        }
    }
    return 0;
}