Untitled

mail@pastecode.io avatar
unknown
plain_text
9 days ago
2.6 kB
3
Indexable
Never
#include <bits/stdc++.h>
using namespace std;

#define int long long
const int MAXN = 2e5 + 5;
const int LOGN = 31;

int n, x;
int a[MAXN];
int prefix_xor[MAXN];
int sparse[MAXN][LOGN];
int logs[MAXN];

void build_sparse_table() {
    for (int i = 0; i < n; i++)
        sparse[i][0] = a[i];
    
    for (int j = 1; j < LOGN; j++) {
        for (int i = 0; i + (1 << j) <= n; i++) {
            sparse[i][j] = __gcd(sparse[i][j-1], sparse[i + (1 << (j-1))][j-1]);
        }
    }
    
    logs[1] = 0;
    for (int i = 2; i <= n; i++)
        logs[i] = logs[i / 2] + 1;
}

int query_gcd(int l, int r) {
    int j = logs[r - l + 1];
    return __gcd(sparse[l][j], sparse[r - (1 << j) + 1][j]);
}

pair<int, int> find_maximum_gcd_length() {
    build_sparse_table();
    map<int, vector<int>> mp;
    mp[0].emplace_back(-1);  
    int val = 0;
    pair<int, int> ans = {-1, -1};
    int max_len = 0, max_gcd = 0;
    
    for (int i = 0; i < n; i++) {
        val ^= a[i];
        int other_val = val ^ x;
        if (mp.find(other_val) != mp.end()) {
            int end = i;
            if(query_gcd(mp[other_val].back()+1,i) > max_gcd)
            {
            	max_len = i - mp[other_val].back();
            	ans = {mp[other_val].back()+2, end+1};
            }
        	max_gcd = max(max_gcd,query_gcd(mp[other_val].back()+1, end));
            int l = 0, r = mp[other_val].size() - 1, best_idx = -1;
            while (l <= r) {
                int mid = (l + r) / 2;
                int start = mp[other_val][mid] + 1;
                int g = query_gcd(start, end);
                if (g > max_gcd || (g == max_gcd && (end - start + 1) > max_len)) {
                    max_gcd = g;
                    max_len = end - start + 1;
                    ans = {start + 1, end + 1}; 
                    best_idx = mid;
                }
                if (g >= max_gcd) {
                    r = mid - 1; 
                } else {
                    l = mid + 1;
                }
            }
        }
        mp[val].emplace_back(i);
    }
    
    return ans;
}

int32_t main() {
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
    #endif

    int t;
    cin >> t;
    while (t--) {
        cin >> n >> x;
        for (int i = 0; i < n; i++)
            cin >> a[i];
        
        pair<int, int> result = find_maximum_gcd_length();
        cout << result.first << ' ' << result.second << '\n';
    }
    
    return 0;
}
Leave a Comment