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;
}

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

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.

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

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