DUMPLING - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

Given two integers A and B, let us try to figure out all the reachable integers. Consider jumping X units to the right as adding X and jumping X units to the left as subtracting X. Working out an example always helps.

If A = 4 and B = 6, observe that we can only reach every integer in the set { …, -8, -6, -4, -2, 0, 2, 4, 6, 8, … }

If A = 3 and B = 5, observe that we can only reach every integer in the set { …, -3, -2, -1, 0, 1, 2, 3, … }

If you try out other simple examples, soon you will be able to notice that given A and B, one can only reach integers that are multiples of the greatest common divisor (gcd) of A and B. Another way of looking at this is that every integer P that satisfies, Ax + By = P, is reachable. Here x and y are arbitrary integers. [ x=2 means that the chef jumps 2A units to the right, x=-5 means he jumps 5A units to the left]. It can be proved that P is a multiple of the gcd of A and B.

Thus, Chef Shifu can reach multiples of the gcd of A and B. Let X = gcd(A,B). Chef Po can reach multiples of the gcd of C and D. Let Y = gcd(C,D). Thus, every multiple of X which is also a multiple of Y can always be reached by both the chefs. If we find the least common multiple of X and Y, say L, then every multiple of L can be reached by both.

Know more about Greatest Common Divisor and Least Common Multiple.

Coming back to the solution - count all the positive reachable integers in the interval (0,K]. This is simply K/L. The number of negative reachable integers must be same due to symmetry. And don’t forget to add the center point too. So the answer is 2 * (K/L) + 1. Here, the only problem was that L may not fit into a 64-bit integer but the final answer would always fit into a 64-bit signed integer. This could be handled by a simple repeated division.

From the definition of the least common multiple, we have L = (X * Y)/gcd(X,Y) , this is same as, S = X/gcd(X,Y) , L = S*Y

T = K/L = K/(S * Y), this is same as, R = K/S , T = R/Y

Thus, all the intermediate results could fit into 64-bit integers. Or you could learn to use your favorite library that handles large integers :).

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

1 Like

If we find the least common multiple of X and Y, say L, then every multiple of L can be reached by both.
In this line above ^^
it should instead have been GCD of X, Y say L.

L=hcf(hcf1,hcf2);
//replace hcfi for i=(1,2) with gcdi and hcf with gcd.