How I solved GCDMOD

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)\%(A-B)
var = [(A^N)\%(A-B) + (B^N)\%(A-B)]\%(A-B)

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)

Link to my solution

If you have any doubts or think I went wrong somewhere please do tell me. Hope this helps other coders.

You can use the built-in pow function for fast modular exponentiation in Python. With Python 3.5 or above you can also use the math.gcd function.

1 Like

thanks. Will solve using these now. :smiley:

Can you tell me what’s wrong in my solution?

https://www.codechef.com/viewsolution/19655465

Python power (⌐■_■)

1 Like

It is due to test case such as this.
1231232111 22801763489 123213
Here C++ long long int is overflowing, even unsigned will overflow. Technique works in my code due to programming language.
Will look into how to counter this and reply back.

It is due to test case such as this.
1231232111 22801763489 123213
Here C++ long long int is overflowing, even unsigned will overflow. Technique works in my code due to programming language.
Will look into how to counter this and reply back.

Rocks.

I prefer to switch to python whenever I see these type of questions.

Thanks for your effort :slight_smile: