WA in MAXLCM

help
1

#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define vi vector
#define vii vector<vector>
#define pb push_back
#define mp make_pair
#define ii pair<int,int>
#define loop(n) for(int i=0; i<(int)n; i++)
#define ld long double
#define um unordered_map
#define test int t; cin>>t; while(t–)
#define floatdigit(n) cout<<fixed; cout<<setprecision(n);
#define all(array) array.begin(),array.end()
#define MOD 1000000007
#define MAX 100005
#define endl “\n”
//USE transform(s.begin(),s.end(),s.begin(),::tolower);
int32_t main(){
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

test{
    int n , m;
    cin>>n>>m;

    vi a(n);

    loop(n){
        cin>>a[i];
    }

    sort(all(a));

    int lcm = a[0];

    for(int i = 1; i < n; i++){
        lcm = (lcm*a[i])/(__gcd(lcm , a[i]));
    }

    unordered_map<int , int> mapi;
    vi store;

    for(int i  = m; i >= 1; i--){

        int lcmTemp = (lcm*i)/(__gcd(lcm , i));

        mapi[lcmTemp] = i;
        store.pb(lcmTemp);
    }

    sort(store.rbegin() , store.rend());
    cout<<mapi[store[0]]<<endl;

}

return 0;

}

2

When you use lcm, you multiply all the numbers which causes overflow.
Even if you use long long int, it will overflow.

So, This is why you are getting WA.

3

Then , whats the solution bro ??

4

you should store the frequency of all prime factors of all input numbers.
Take an array called LCM all initialized to 0 ,and start processsing from the first element
when the freqency of an prime factor of the element is more than the number stored in LCM array the replace the number in the LCM array with frequency of prime factor of that element.
at last LCM array will contain all the freqency of prime factor of the resultant LCM.

for for the element to be appended , take a loop form m … 1 and calculate increment in LCM and if for any number LCM is highest , replace answer with the element

5

You can read Editorial now :slight_smile: