 # PRODUCT - Editorial

Setter: Lavish Gupta
Tester: Abhinav Sharma, Aryan
Editorialist: Lavish Gupta

Simple

None

# PROBLEM:

Given two positive numbers B and C, what is the minimum positive value of A, such that A \cdot B is divisible by C.

Here, A \cdot B denotes the value obtained when A is multiplied by B.

# EXPLANATION:

Let say A \cdot B = \lambda \cdot C, where \lambda \geq 1 and \lambda is an integer. We want to find out the minimum value of A such that the above equation holds.

A = \frac{\lambda \cdot C}{B}

To minimize A, we want to find out the minimum value of \lambda such that \frac{\lambda \cdot C}{B} is an integer. Let gcd(B, C) = g. So, we have C = c \cdot g and B = b \cdot g, where b and c are co-prime.

Substituting this back, we have A = \frac{\lambda \cdot c}{b} = \frac{\lambda}{b} \cdot c. The minimum value of \lambda such that \frac{\lambda}{b} is an integer is b. So we have A = c = \frac{C}{g}.

# TIME COMPLEXITY:

O(1) for each test case.

# SOLUTION:

Editorialist's Solution
#include<bits/stdc++.h>
#define ll long long
using namespace std ;
ll gcd(ll a , ll b){ if(b > a) return gcd(b , a) ; if(b == 0) return a ; return gcd(b , a%b) ;}

int main()
{
ll t;
cin >> t ;
while(t--)
{
int b , c ;
cin >> b >> c ;
cout << c/gcd(b,c) << '\n' ;
}

return 0;
}



I have put the exact same solution here: Solution: 59025945 | CodeChef. Any reason why the second test case gives TLE for me ?

https://www.codechef.com/viewsolution/59002335

what’s wrong in my solution please anyone help.

signed int overflow, use long long

why are you using int?? problem constraints says large data set (10^9) which suggests you to use long long. after using long long in your code it’s accepted. try yourself and see Bro try to take long long or unsigned long long for such cases make sure to properly look for the constraints mentioned in the question .

https://www.codechef.com/viewsolution/58908516

why i am getting tle ???

no need to use long long…int can obviously store 10^9. just don’t do the unnecessary multiplication at the end… just do (b/t). it’ll work with int.

1 Like

worst-case time complexity: O(10^5 *10^9) which is 10^14.
Roughly 10^9 operations are possible in 1 sec.
Hence TLE.

1 Like

https://www.codechef.com/viewsolution/58931365

Can anyone please help me to find the reason for the failure of my solution to the given test cases.

https://www.codechef.com/viewsolution/59076262
I have tried with long long also instead of int but no change is there , it is showing error in test case-2.
what’s wrong in my solution please anyone help.

@lavish_adm This issue has been bugging me for quite sometime now, could you please help ? Original question was posted on the date of the contest. PRODUCT - Editorial - #2 by aelor

Lcm(b,c)/b is also the same thing , then why it is giving WA on this and accepting the answer for c/gcd(b,c)

#include<bits/stdc++.h>
using namespace std;

int main()
{
int t;
cin >>t;
while(t–)
{
int b,c;
cin>>b>>c;

    //   long long int a=(long long int)lcm(b,c);
cout<<lcm(b,c)/b<<endl;

}


}

Hey!
In my second test case I am getting TLE problem.Please help me to fix this. I am a new to this coding world so my code may be very basic so applogize for that. I am able to understand the solution but I need to know what is wrong with my code .
https://www.codechef.com/viewsolution/58965191