MAX LCM QUESTION OF MARCH LUNCHTIME!

help
1

i don’t know whats the mistake in my code i have tested more than 100 cases manually and all of them giving correct answer please help!!!

Here is my code–

#include<bits/stdc++.h>
using namespace std;
#define ll long long int

ll gcd(ll a, ll b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}

ll findlcm(ll arr[], ll n)
{
ll ans = arr[0];

for (ll i = 1; i < n; i++) 
    ans = (((arr[i] * ans)) / 
            (gcd(arr[i], ans))); 

return ans;

}

// Function to return LCM of two numbers
ll lcm(ll a, ll b)
{
return (a*b)/gcd(a, b);
}

int main(){

ll num;
cin>>num;

while(num–){

ll n,k;
cin>>n>>k;
ll arr[n];
for(ll i=0;i<n;i++){
cin>>arr[i];
}

ll ans = findlcm(arr,n);

ll fin=0;

ll temp=ans;

for(int i=k;i>=1;i–){

ll val = lcm(ans,i);
if(val>=temp){
fin =i;
temp =val;
}

}

cout<<fin<<"\n";

}

return 0 ;
}

2

When you use lcm, you multiply all the numbers which causes overflow.
Even if you are using long long int, it is overflowing.

So, This is why you are getting WA.

P.S:- Check out about cpp_int and other int types of boost (however this will also give you partially correct answer because finding gcd is of logn).

3

I tried it using unsigned long long int (largest data type) but still it’s giving me WA is it still be the case of interger overflow? or there is some logic error

4

You can store the lcm value into power of primes and try.

2 Likes
5

No Even if you use unsigned long long int, it wil still overflow because you are multiplying too many numbers … even if you multiply 7 & 11, It gives 77 as result now you can think.

P.S:- Check Out cpp_int and other int data type of boost (however it will give you PA because finding gcd takes logn).

1 Like
6

Can you please elaborate the logic?

7

Check my reply here Maximize LCM lunchtime,my code giving WA

8

Your soluion will result in an overflow. Try using factorization as every number can be expressed as the product of primes. Look at this once. I think it will be clear.
https://www.codechef.com/viewsolution/30855235