Coding problem

[SparkXV]

Can somebody explain why i am getting the wrong answer?
https://www.codechef.com/FEB19B/problems/HMAPPY2

  
#include <iostream> 
using namespace std; 
  
long long int gcd(long long int a, long long int b) 
{ 
    
    if (b == 0) 
        return a; 
    return gcd(b, a % b);  
}
  
int main()
{
       long long int n,a,b,r,i,m,t,k,p,q;
       cin>>t;
       while(t--)
       {
          cin>>n>>a>>b>>k;
          p=(n/a);
          q=(n/b);
          r=(a*b)/gcd(a,b);
          m=(n/r);
          if((p+q-m)>=k)
             cout<<"Win"<<"\n";
          else
             cout<<"Lose"<<"\n";
       }
    return 0;
}

[dhayden]

Did you test your gcd() function? Here is a program with indentation that reflects the actual block structure and a few tests of gcd(). Seen this way, it's pretty clear that gcd() isn't right. For one thing, it never gets past line 13.

#include <iostream>
using namespace std;

long long int
gcd(long long int a, long long int b)
{

    if (a == 0)
	return b;

    if (b == 0)
	return a;
    return a;

    if (a == b)

	if (a > b)
	    return gcd(a - b, b);
    return gcd(a, b - a);
}

int
main()
{
    cout << gcd(10, 13) << '\n';
    cout << gcd(10, 2) << '\n';
    cout << gcd(33, 11) << '\n';
    return 0;
}

And this is the output, which verifies that gcd() isn't working right.

10
10
33

[dutch]

Your gcd implementation is incorrect. Not only do you have a misplaced "return a" that causes it to return a if neither a nor b are 0, but it uses subtraction where it would normally use the modulus op. A more usual recursive implementation is:

long long int gcd(long long int a, long long int b) 
{
    return b == 0 ? a : gcd(b, a % b);
}

However, I don't think that's the way to solve the problem. It's really just a matter of calculating how many numbers up to and including N are divisible by A, how many are divisible by B, and how many are divisible by A * B. With that you can solve the problem.

[SparkXV]

@dutch @dhayden Initially my code got misplace now i edited it.Why it is giving the wrong answer for the test case?

[jonnin]

gcd is in algorithm as __gcd
coding it yourself just makes it slower. I can't comment on whether you need it here, I can't go to codechef from work.

[SparkXV]

My approach:

Numbers divisible by a + Numbers divisble by b -(Number of common multiples) >=k

Is above approach is wrong?

[dutch]

If it's giving the wrong answer, then it must be wrong. I was thinking of this:

#include <iostream> 

int main()
{
    int t;
    std::cin >> t;
    while (t--)
    {
        int n, a, b, k;
        std::cin >> n >> a >> b >> k;
        int na = n / a;
        int nb = n / b;
        int nab = n / (a * b);
        if (na + nb - 2 * nab >= k)
            std::cout << "Win\n";
        else
            std::cout << "Lose\n";
    }
}

Note that the ones divisible by a*b (nab) are counted in both na and nb, so you need to subtract twice nab.

[SparkXV]

@dutch Tanks.But i already got it.

[dutch]

I don't believe you. :-)