Untitled
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