can someone provide Editorial for CURREQ of procon ?
For simplicity I am changing the currency to Rupees, Dollars and Yen
Problem: Given S, X, Y, Z its known that S dollars = X rupees and Y rupees = Z yen,find A, B, C such that A dollars = B rupees = C Yen
Explanation: You have to first reduce S and X, and Y and Z to their lowest irreducable forms. Like…suppose its given that 11 dollars = 22 rupees, then make it 1 dollar = 2 rupees, else you will not get the minimum A, B, C. To do that we have to divide both S and X with gcd(S, X) and divide Y and Z with gcd(Y, Z). Now we have to multiply X with something and Y with something so that they are equal. How can we do that? We know that we can always multiply X and Y with something to make it equal to LCM(X, Y). So we find LCM(X, Y), then we make X as LCM(X, Y). Since we multiplied X with LCM(X, Y)/X, we need to multiply S with LCM(X, Y)/X too. Same argument goes for changing Y and Z too. So overall, we get A = S*LCM(X, Y)/X , C = S*LCM(X, Y)/Y, B = LCM(X, Y).
Feel free to comment any queries that you have
Thank you for your explaination, it helped me to understand concept behind it.