R☆

我重生了,重生在了IOI考前的一天。上一世我 AK 了 IOI，却被柳如烟陷害，禁赛了114514年。这一世,我要拆穿柳如烟，夺回属于我的一切!

#include<iostream>
#include<map>
using namespace std;
map<long long ,long long > pri,cou;
long long t,n,m,a[100008],vis[1000008],b[100008],xhash[1000008],k,ans=0,ansl,ansr;
int hhash(long long x){
	if(pri[x]!=0) return pri[x];
	else pri[x]=rand();
	return pri[x];
}
void prime(){
    for(int i=2;i<=1000000;i++){
        if(vis[i]==0){
            int k=hhash(i)+1;
            for (int j=i;j<=1000000;j+=i){
                vis[j]=1;
                int jj=j;
                while(jj%i==0&&jj!=0){
                    xhash[j]^=k;
                    jj/=i;
                }
            }
        }
    }
    xhash[1] = 0;
}
void solve(){
	ans=0;ansl=0;ansr=0;
	cou.clear();
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=b[i-1]^xhash[a[i]];
		if(b[i]==0){
			if(i>ans){
				ansl=0,ansr=i,ans=i-cou[b[i]];
			}
		}else if(cou[b[i]]!=0){
			if(i-cou[b[i]]>ans){
				ansl=cou[b[i]],ansr=i,ans=i-cou[b[i]];
			}else if(i-cou[b[i]]==ans&&cou[b[i]]+1<ansl){
                ansl=cou[b[i]];
                ansr=i;
            }
		}
		else cou[b[i]]=i;
	}
	if(ansr!=0) cout<<ansl+1<<' '<<ansr<<'\n';
	else cout<<"-1 -1"<<'\n';
}
int main(){
	freopen("seq.in","r",stdin);
	freopen("seq.out","w",stdout);
	srand(14234);
	prime();
	cin>>t;
	while(t--) solve();
}/*
5
10
1 4 9 16 25 36 49 64 81 100
10 
2 3 6 1 2 8 7 7 2 2
10
1 1 1 1 1 1 1 1 1 1 
10 
2 2 2 2 2 2 2 2 2 2
10
2 3 5 7 11 13 17 19 23 29
*/