https://www.codechef.com/problems/SUBLCM

i have tried two pointer technique to solve this question. I checked for a valid sub-array where LCM(sub-array) == product(sub-array ) but i am getting WA . any help would be appreciated .

ll gcd(ll a,ll b){return __gcd(a,b);}
ll lcm(ll a,ll b){return (a*b)/(gcd(a,b));}

void solve(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
vl arr(n);
frep(i,0,n,1){cin>>arr[i];}
int ans=-1,l=0,r=0;
ll cpro=1,clcm=1;
frep(i,0,n,1){
cpro*=arr[i];
clcm=lcm(clcm,arr[i]);
if(cpro==clcm){
ans=max(ans,i-l+1);
}
else{
cpro=arr[i];
clcm=arr[i];
l=i;
}

}
if(ans==1){ans=-1;}
cout<<ans<<endl;
}
}


Overflow

will uint_64 cut it or i need to change the approach ?

ill just try it out thanks

It won’t.

Spoiler

There are 10^5 numbers up to 10^6 so it may go up to \approx 10^{6 \times 10^5}
Notice that all numbers in your window must be pairwise coprime.

yeah had thought about that initially . thanks for the insight though :=)

https://www.codechef.com/viewsolution/33714823
This is my AC solution one thing i wanna ask If i run this solution on my local machine (codeblocks or Devcpp) then it show exit run status ( as i define MAX = 1000002) and same thing happen on online compiler too…but it AC on codechef…how can i remove these type of things …sometime it happens in ongoing contests too i make solution which is valid (in terms of complexity ) but when i run on my machine or on online compiler then it show command signal terminated, exit status …help @everule1 @galencolin

The best solution is to get a better compiler

A dangerous solution is to, for local purposes, define MAX to be like 1002 or something. You can mess with #ifdef and set some local compilation flags so it’s 1002 locally and 1000002 when submitting anywhere else.

1 Like