GETTING WA IN MXMLCM PLEASE HELP!

PROBLEM LINK-Contest Page | CodeChef
MY SOLUTION-
#include <bits/stdc++.h>
#include
#include
#include
#include
using namespace std;
long long gcd(long long a, long long b)
{
if(b==0)
{
return a;
}
else
return gcd(b,a%b);
}

int main()
{
int t;
cin>>t;
while(t–)
{
long long n,m;
long long lcm=1;
cin>>n>>m;
for(int i=0;i<n;i++)
{
long long a;
cin>>a;
lcm=(lcm*a)/(gcd(lcm,a));
}

    if((lcm%m)==0){
        if(m!=1)
        cout<<m-1<<endl;
        else
            cout<<m<<endl;
        }
    else
        cout<<m<<endl;


}

return 0;
}

Ur algorithm is not general friend. It will satisfy only few cases,
Try this ,I hope u understand the code .

import java.util.Scanner;

public class MaxLCM {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-- > 0) {
int n = sc.nextInt();
int m = sc.nextInt();
int a[] = new int[n];
for (int j = 0; j < n; j++) {
a[j] = sc.nextInt();
}

  System.out.println(maxLcm(a, m));
}
sc.close();

}

public static int maxLcm(int a[], int m) {

if (m == 1 && m == 2) {
  return 1;
}

int ans = 0;
long maxLCM = 0;
long lcm = a[0];
long gcd = a[0];

for (int i = 1; i < a.length; i++) {
  gcd = GCD(a[i], lcm);
  lcm = (lcm * a[i]) / gcd;
}

for (int k = 1; k <= m; k++) {
  gcd = GCD(k, lcm);
  if ((lcm * k) / gcd > maxLCM) {
    maxLCM = (lcm * k) / gcd;
    ans = k;
  }
}
return ans;

}

public static long GCD(long a, long b) {

if (b == 0) return a;

return GCD(b, a % b);

}
}

Bro, i am still not able to understand where my approach is wrong .Can you please give a case where my code will fail?

1 Like

Ur code will run good if the number previous to m is prime because it will not be factorised further

Try this case bro
3 9
2 5 9
I guess it may give wrong output as far as I understood ur code.

Yes bro got it, thanks a lot.

1 Like