DUMPLING: Getting wa

hey I m having a prob in d problem-http://www.codechef.com/APRIL12/problems/DUMPLING
Here is my code- http://www.codechef.com/viewsolution/983332
The hcf and lcm functions as well as d algo is correct. It seems that the order in which i am doing d calculations is leading me to a wrong answer.
When i do this, it gets a right answer-

while(t--)
{
    scanf("%llu %llu %llu %llu %llu",&a,&b,&c,&d,&k);
    h1=hcf(a,b);
    h2=hcf(c,d);
    h3=hcf(gcd1,gcd2);
    l=k*h3;
    l/=h1;
    l/=h2;
    printf("%llu\n",l*2+1); //since k=0 is always a solution a to left, a to right
}

But this causes a wrong answer-

 while(t--)
    {
        scanf("%llu %llu %llu %llu %llu",&a,&b,&c,&d,&k);
        l=lcm(hcf(a,b),hcf(c,d));  //lcm as defined in above url
        printf("%llu\n",(k/l)*2+1); //since k=0 is always a solution a to left, a to right
    }

Why is this happening cos they both essentially lead to the same expression

When we run the code for 1 10^18 10^18 10^18 10^18 10^18 (the worst case) …

here is what happens… when u calculate lcm. as u know LCM(a,b)=a*b/gcd(a,b);

a*b = 10^36. but c or c++ supports only to 10^18 (OVERFLOW CASE)…

so u have to optmize ur solution to do that…

2 Likes

hey thanks!!!

my pleasure !!! :slight_smile: