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 $$ (a*b)\%m = (a\%m * b\%m)\%m $$ $$ (a*b)\%m = (a\%m + b\%m)\%m $$ 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 $$(A^N + B^N)\%(AB)$$ $$ var = [(A^N)\%(AB) + (B^N)\%(AB)]\%(AB)$$ Now $(A^N)\%(AB)$ or $(B^N)\%(AB)$ 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 $(AB)$ 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. asked 13 Aug '18, 17:37

You can use the builtin
pow
function for fast modular exponentiation in Python. With Python 3.5 or above you can also use themath.gcd
function.thanks. Will solve using these now. :D
Python power (⌐■_■)
Rocks.
I prefer to switch to python whenever I see these type of questions.