×

# How I solved GCDMOD

 0 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. asked 13 Aug '18, 17:37 4★ay2306 232●9 accept rate: 11% 1 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. (13 Aug '18, 18:57) meooow ♦6★ thanks. Will solve using these now. :D (13 Aug '18, 19:15) ay23064★ 1 Python power (⌐■_■) (13 Aug '18, 19:24) meooow ♦6★ Rocks. I prefer to switch to python whenever I see these type of questions. (13 Aug '18, 21:13)

 0 Can you tell me what's wrong in my solution? https://www.codechef.com/viewsolution/19655465 answered 13 Aug '18, 19:21 1 accept rate: 0% 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. (13 Aug '18, 20:05) ay23064★ 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. (13 Aug '18, 20:08) ay23064★
 0 Thanks for your effort :) answered 25 Jan, 01:04 0★oaik 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,723
×1,424
×321

question asked: 13 Aug '18, 17:37

question was seen: 1,460 times

last updated: 25 Jan, 01:04