You are not logged in. Please login at www.codechef.com to post your questions!

×

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.

asked 13 Aug '18, 17:37

ay2306's gravatar image

4★ay2306
2329
accept rate: 11%

edited 13 Aug '18, 17:40

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) aryanc4035★

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

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

link

answered 13 Aug '18, 19:21

codechefnew's gravatar image

3★codechefnew
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★

Thanks for your effort :)

link

answered 25 Jan, 01:04

oaik's gravatar image

0★oaik
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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