Simple code
/**
* Coded by : lucky_21
* --------Lokesh Singh
**/
#include<bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T> using oset=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
#define F first
#define S second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define fix fixed<<setprecision(10)
#define rep(i,a,b) for(int i=int(a);i<=int(b);i++)
#define repb(i,b,a) for(int i=int(b);i>=int(a);i--)
#define FastIO ios_base::sync_with_stdio(0),cin.tie(0)
typedef double db;
typedef long long ll;
const int N=2e5+5;
const int mod=1e9+7;
int n,ans,f[55];
map<string,int>m;
signed main(){
FastIO;
string tp(55,'0');
m[tp]=0;
vector<int>p;
rep(i,2,250){
bool ok=1;
rep(j,2,i-1) if(i%j==0) ok=0;
if(ok) p.pb(i);
}
cin>>n;
rep(i,1,n){
int a;
cin>>a;
rep(j,0,p.size()-1){
int cnt=0;
while(a%p[j]==0){
cnt++;
a/=p[j];
}
f[j]=(f[j]+cnt)%2;
}
string s;
rep(i,0,54) s+=to_string(f[i]);
if(!m.count(s)) m[s]=i;
else ans=max(ans,i-m[s]);
}
cout<<ans;
return 0;
}
Efficient code using tries
//Jai Sai Ram
// Always keep helping me while debugging and solving my life.
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
string arr[100001];
ll smallest_prime[2000001];
void seive()
{
ll i,j,k,l,m,n,o,p;
for(i=1;i<=2000000;i++)
{
smallest_prime[i]=1;
}
smallest_prime[0]=smallest_prime[1]=1;
for(i=2;i<=2000000;i++)
{
if(smallest_prime[i]==1)
{
for(j=2*i;j<=2000000;j+=i)
{
if(smallest_prime[j]==1)
smallest_prime[j]=i;
}
smallest_prime[i]=i;
}
}
}
vector<pair<ll,ll>> prime_divisors(ll n)
{
ll i,j,k,l,m,o,p,q,r,s,t;
vector<pair<ll,ll>> vp;
if(n<=1)
return vp;
while(n!=1)
{
p=0;
k=smallest_prime[n];
while(n%k==0)
{
n/=k;
p++;
}
if(p>0)
vp.push_back(make_pair(k,p));
}
if(n>1)
{
vp.push_back({n,1});
}
return vp;
}
struct Trie{
Trie *chars[2];
bool is_end;
ll count=0;
ll position=-1;
};
Trie *create()
{
Trie *ro=new Trie;
ro->is_end=false;
for(ll i=0;i<2;i++)
{
ro->chars[i]=NULL;
}
ro->count=0;
ro->position=-1;
return ro;
}
void insert(Trie *root,string key,ll pos)
{
Trie *temp=root;
for(ll i=0;i<key.length();i++)
{
ll index=(key[i]-'0');
if(!temp->chars[index])
{
temp->chars[index]=create();
}
temp->chars[index]->count++;
temp=temp->chars[index];
}
temp->is_end=true;
temp->position=pos;
}
ll search(Trie *root,string key)
{
Trie *temp=root;
for(ll i=0;i<key.length();i++)
{
ll index=(key[i]-'0');
if(!temp->chars[index])
{
return -1;
}
temp=temp->chars[index];
}
if(temp!=NULL&&temp->is_end==true)
{
return temp->position;
}
return -1;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
Trie *root=new Trie;
root=create();
ll t,i,j,k,l,m,n,o,p,q,r,a[300001];
cin>>n;
memset(arr,0,sizeof(arr));
seive();
ll ans=0;
a[0]=0;
string s="";
for(i=0;i<=250;i++)
{
s+='0';
}
insert(root,s,0);
arr[0]=s;
for(i=1;i<=n;i++)
{
cin>>a[i];
vector<pair<ll,ll>> vp=prime_divisors(a[i]);
s=arr[i-1];
for(auto it:vp)
{
k=it.first;
l=it.second;
m=s[k];
m-=48;
l=l%2;
l+=m;
l%=2;
s[k]=(char)(l+48);
}
arr[i]=s;
// cout<<s<<endl;
if((p=search(root,s))!=-1)
{
//cout<<p<<endl;
ans=max(ans,i-p);
}
else
{
insert(root,s,i);
}
}
cout<<ans<<endl;
return 0;
}
, BTW nice questions 