Why brute force approach gives WA in Maximize Lcm (MXMLCM)?

help
1

#include<stdio.h>
#include <bits/stdc++.h>
using namespace std;
//Fuctions for calculating LCM
typedef long long int ll;
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
ll findlcm(int arr[], int n)
{
ll ans = arr[0];
for (int i = 1; i < n; i++)
ans = (((arr[i] * ans)) /
(gcd(arr[i], ans)));

return ans;

}

int main()
{ int i,T,n,m,a[10002],lcm,lcmnew,prevlcm,b[2],ans;
scanf("%d",&T);
while(T–){
ans=1;
scanf("%d %d",&n,&m);
for(i=0;i<n;i++){
scanf("%d",&a[i]);
}

		lcm=findlcm(a,n);
		prevlcm=lcm;

		b[0]=lcm;

		for(i=1;i<=m;i++){
			b[1]=i;
			lcmnew=findlcm(b,2);
			if(lcmnew>plcm)
				{plcm=lcmnew;
				 ans=i;
				 }
			
			}
		printf("%d\n",ans);
	}
return 0;

}

2

ans in LCM will overflow, you cant use this approach

3

lcm exceeds limit of integer.
HINT: Find LCM in terms of prime factorization.

1 Like