算法

(数论) $O(t * n * \max\{a_i\})$

显然最大长度是相邻两数的 gcd 的最大值 mx
注意到题目让我们求的是最长子数组的长度，而不是子列，所以直接枚举 mx 的倍数的做法是错误的
正确做法是可以开一个变量 $cnt$ 来记录当前这段 gcd 都为 mx 的区间长度，如果下一个元素不是 mx 的倍数，则将 $cnt$ 赋为 $0$ 并重新开始找，然后找最长的那段区间。

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()

using std::cin;
using std::cout;
using std::vector;
using std::max;
using P = std::pair<int, int>;
template<typename T> using vc = vector<T>;
using vi = vc<int>;
using vp = vc<P>;

// linear sieve
vi ps, pf;
void sieve(int mx) {
    pf = vi(mx + 1);
    rep(i, mx + 1) pf[i] = i;
    for (int i = 2; i <= mx; ++i) {
        if (pf[i] == i) ps.pb(i);
        for (int j = 0; j < sz(ps) and ps[j] <= pf[i]; ++j) {
            int x = ps[j] * i;
            if (x > mx) break;
            pf[x] = ps[j];
        }
    }
}

vp factor(int x) { // asc
    if (x == 1) return {};
    vp res(1, P(pf[x], 0));
    while (x != 1) {
        if (res.back().fi == pf[x]) res.back().se++;
        else res.pb(P(pf[x], 1));
        x /= pf[x];
    }
}

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        rep(i, n) cin >> a[i];
        int mx = 0;
        for (int i = 1; i < n; ++i) mx = max(mx, std::gcd(a[i], a[i - 1]));
        int ans = 0, cnt = 0;
        rep(i, n) {
            if (a[i] % mx == 0) ++cnt;
            else cnt = 0;
            ans = max(ans, cnt);
        }
        cout << mx << " " << ans << '\n';
    }

    return 0;
}