Untitled

 avatar
unknown
c_cpp
9 months ago
3.1 kB
7
Indexable
#include <bits/stdc++.h>
using namespace std;

#define ll long long int
#define pb push_back
#define ff first
#define ss second
#define mp make_pair
#define all(v) v.begin(), v.end()
#define uniq(v) (v).erase(unique(all(v)), (v).end())
#define rep(i, m, n) for (int i = m; i < n; i++)
void __print(int x)
{
    cerr << x;
}
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }

template <typename T, typename V>
void __print(const pair<T, V> &x)
{
    cerr << '{';
    __print(x.first);
    cerr << ',';
    __print(x.second);
    cerr << '}';
}
template <typename T>
void __print(const T &x)
{
    int f = 0;
    cerr << '{';
    for (auto &i : x)
        cerr << (f++ ? "," : ""), __print(i);
    cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v)
{
    __print(t);
    if (sizeof...(v))
        cerr << ", ";
    _print(v...);
}
#ifndef ONLINE_JUDGE
#define debug(x...)               \
    cerr << "[" << #x << "] = ["; \
    _print(x)
#else
#define debug(x...)
#endif

ll mod = 1000000007;

const int N = 2e5 + 10;
const int M = 64;
ll tab[N][M];

void SparseTable(vector<ll> v, ll n) // For Max,Min,Gcd
{
    for (int i = 0; i < n; i++)
    {
        tab[i][0] = v[i];
    }
    for (int j = 1; (1 << j) <= n; j++)
    {
        for (int i = 0; (i + (1 << j) - 1) < n; i++)
        {
            tab[i][j] = __gcd(tab[i][j - 1], tab[i + (1 << (j - 1))][j - 1]);
        }
    }
}
ll query(ll l, ll r)
{
    int j = (int)log2(r - l + 1);
    return __gcd(tab[l][j], tab[r - (1 << j) + 1][j]);
}

bool ok(ll mid, ll n)
{
    for (int i = 0; i + mid - 1 < n - 1; i++)
    {
        if (query(i, i + mid - 1) > 1)
        {
            return 1;
        }
    }
    return 0;
}
void solve()
{
    ll n;
    cin >> n;
    vector<ll> v(n), diff(n - 1);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }
    for (int i = 0; i < n - 1; i++)
    {
        diff[i] = abs(v[i] - v[i + 1]);
    }
    debug(diff);
    SparseTable(diff, n - 1);
    ll low = 1, high = n;
    ll ans = 0;
    while (low <= high)
    {
        ll mid = (low + high) / 2;
        if (ok(mid, n))
        {
            ans = mid;
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }
    cout << ans + 1 << '\n';
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll tt;
    cin >> tt;
    while (tt--)
        solve();
}
Editor is loading...
Leave a Comment