It took me days to come up with a solution to GCDMOD, so I wish to share it with people with the complete approach on how I did it.
Step 1: Choosing the algorithm to calculate gcd of two numbers
This was a crucial step, I was confused between using a library for big integers or something. But when the idea clicked, I found out that normal Euclidean GCD was enough (Note normal one, not extended one)
Step 2: Tweaking the algorithm
Now next step is to tweak the algorithm so that we can get out desired results. For this, we will use two properties from modular mathematics which are
Now we know that the first step of the Euclidean GCD algorithm is that we recall gcd(b%a, a).
Step 3: The remaining workout
Now let’s solve the question for A, B, N, and A \neq B
As we discussed we will first step of the Euclidean algorithm will be
Now (A^N)\%(A-B) or (B^N)\%(A-B) can be calculated using modular exponentiation
Now all left is to var we calculated is within the range of long long int and now just have to calculate gcd with (A-B)
Step 4: Checking edge cases
In this approach, there is only one edge case that is A = B. When this happens, the answer is simple 2 \times(A^N \% 1000000007)
If you have any doubts or think I went wrong somewhere please do tell me. Hope this helps other coders.
