WA in the problem The product mystery

#include <iostream>
using namespace std;

int main() {
	// your code goes here
	int t;
	cin>>t;
	while(t--){
	    int b,c;
	    cin>>b>>c;
	    int i=1;
	    while(c%b!=0){
	        i++;
	        c=c*i;
	    }
	    cout<<c/b<<"\n";
	}
	return 0;
}

This code is giving me a wrong answer for test case 2 for problem :https://www.codechef.com/START27C/problems/PRODUCT . Why ?

Your idea is wrong bro.try to implement another idea
for this test case your code is giving negative answer

10
73 6
95 38
41 91
6 13
59 67
98 27
62 95
33 62
43 95
81 36

check the problem constraints it’s large number but your code failing on large data set. instead of using while try to use straight approach (formula)

I see, but can you tell why it is giving a negative number?

Your approach is wrong and time consuming also. Try to think in different way. if I have two numbers

  1. b=3 ,c=6 then what would be a?? simply 2.
  2. b=7 ,c=8 then what would be a?? simply c.
  3. b=8,c=12 then what would be a??? Simply 3.

Try to think why it is so. If you are able to understand this you will get to know why your program is wrong and what is right logic.

1 Like

I think this will help you!
The concept behind is that: if b is divisible by c, then whatever be the value of a, the product of a and b will always be divisible by c, and as we have to tell the smallest positive value of a, hence a will be 1.
Now if b is not divisible by c, then first we have to find the LCM of b and c, once it is done we will divide it by b which in turn gives us the required smallest positive value of a.
Hope you will understand the below solution:

#include <bits/stdc++.h>
#include <boost/math/common_factor.hpp>
using namespace std;

int main()
{
	long t{};
	cin >> t;
	while(t--){
	    long b{},c{};
	    cin >> b >> c;
	    if(b%c == 0){
	        cout << "1" << endl;
	    }
	    else{
	        cout << (boost::math::lcm(b,c) / b) << endl;
	    }
	}
	return 0;
}
1 Like

Taught me how to fish than to give me a fish, Thanks bro!

Yep lcm seems like a quick and neat idea. Thanks man!