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