PRODUCT - Editorial


Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

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






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.


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


O(1) for each test case.


Editorialist's Solution
#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 ;
        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 ?

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 :slight_smile:

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 .

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

Can anyone please help me to find the reason for the failure of my solution to the given test cases.
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)

using namespace std;

int main()
int t;
cin >>t;
int b,c;

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


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 .