PROBLEM LINK
Author: C Shriram
Editorialist: Kairav Shah
DIFFICULTY
Easy
PREREQUISITES
Basic Number Theory, GCD Calculation
PROBLEM EXPLANATION
The solution to the problem is straightforward.
Since Pragyan can move only in steps of x1 units or x2 units along the x axis and he has an infinite supply of each of the potions, Pragyan’s x-position can be calculated as
x = (a1 X x1) + (a2 X x2)
We know from basic number theory that this number x=a1x1+a2x2 is a multiple of the greatest common divisor of x1 and x2.
The same line of reasoning can be applied to the y coordinate as well.
Thus, we first calculate the GCD of strengths of potions in x direction and y directions in x and y respectively. In each planet, if each coordinate of the scroll is a multiple of the corresponding GCD (both have to satisfy the condition simultaneously), then the scroll in that planet can be retrieved. We can thus calculate the total number of scrolls which can be retrieved.
Calculation of GCD:
We calculate GCD by Euclid’s algorithm.
- Let a>b.
- If b divides a, b is the GCD.
- If b doesn’t divide a, then GCD(a,b) = GCD(b,a-b).
This calculation of GCD can be done in O(log(b)) time.
Checking of each planet:
Each planet can be checked in O(1) time once the GCD has been calculated, and the final condition can be checked in O(1) time.
Thus, the total time taken for each test case is O(N+log(b)+1)=O(N), since log(b)+1 is small compared to N.
The total process thus runs in O(TN) time.