GCDMOD - Editorial

Problem Link



Author: Bhuvnesh Jain

Tester: Mark Mikhno

Editorialist: Bhuvnesh Jain




GCD, Modular Exponentiation, Overflow-handling


Find the GCD of A^N + B^N and (A - B) modulo 1000000007.


The only property required to solve the complete problem is GCD(U, V) = GCD(U % V, V). If you are unfamiliar with this, you can see the proof here.

Now the problem remains finding the value of (A^N + B^N) % (A - B). This is can be easily done using modular exponentiation in O(\log{N}) complexity. You can read about on wikipedia and implementation at Geeks for Geeks.

With the above 2 things, you are almost close to the full solution. The only thing left now is to handle overflows in languages like C++ and Java. First, understand why we might get overflow and then how we handle it.

Note that we are computing A^N % (A - B). Since, (A - B) can be of the order {10}^{12}, the intermediate multiplications during exponentiation can be of the order of {10}^{12} * {10}^{12} = {10}^{24} which is too large to fit in long long data type. Due, to overflows, you will get the wrong answer. To deal with overflows, below are 3 different methods:

  • Using “int_128” inbuilt datatype in C++. For details, you can refer to [mgch solution].

This approach has a complexity of O(1).

  • Using an idea similar to modular exponentiation. Instead of carrying out multiplication operations, we use addition operations. Below is a pseudo-code for it:

	# Returns (a * b) % m
	def mul_mod(a, b, m):
		x = 0, y = a
		while b > 0:
			if b & 1:
				# No overflows in additons.
				x = (x + y) % m
			y = (y + y) % m
			b >>= 1
		return x

This approach has a complexity of O(\log{B}).

  • Using idea similar to karatsuba trick. This is specific only to this question as constraints are upto {10}^{12} and not {10}^{18}. We can split a as a_1 * {10}^{6} + a_2 and b as b_1 * {10}^{6} + b_2. Note that all a_1, b_1, a_2, b_2 are now less than or equal to {10}^{6}. Now we multiply both of them and there will be no overflow now in intermediate multiplications as the maxmium value can be {10}^{12} * max(a_1, b_1) = {10}^{18}. The setter code using this approach.

The time complexity of this approach is O(1).

The final corner case to solve the problem is the case when A = B. This is because calculating A^N + B^N % (A - B), would lead to runtime error while calculating modulo 0. For this case, we use the fact that GCD(U, 0) = U. Thus the answer is simply A^N + B^N.

The last part is just printing the answer modulo 1000000007.

The overall time complexity is O(\log{N} + \log{max(A, B)}). The first is for calculating the modular exponentiation and the second part is for calculating GCD. The space complexity is O(1).

Once, you are clear with the above idea, you can see the author implementation below for help.

Note that since the number of test cases was small, another approach which iterates over divisors of (A - B) to find the answer will also pass within the time limit if proper care is taken of overflows and the case A = B.

Feel free to share your approach as well, if it was somewhat different.

Time Complexity

O(\log{N} + \log{max(A, B)})

Space Complexity



Author’s solution can be found here.

Tester’s solution can be found here.

mgch’s solution can be found here.

1 Like

Author’s solution link is leading to gcd editorial page !

Posted 3 times https://discuss.codechef.com/questions/133408/gcdmod-editorial https://discuss.codechef.com/questions/133409/gcdmod-editorial .

Gives 500 but present on homepage - https://discuss.codechef.com/questions/133407/gcdmod-editorial

Wiki ??

I am getting 500 system error while navigating to other editorials.Can you look into it once.

It turns out that we get the same answer whenever n > 1, so if n >= 2, set n = 2 and print the answer directly. Only special case is a == b, in which the answer is 2 \times a^n. Here’s my AC Submission.
Though I can’t prove it, anyone??

1 Like

answer(a,b,n) for n>=2 is same as answer(a,b,2) [provided a!=b]


for a=b

use modular exponentiation.

Why is everyone’s solution doing mod with (a-b) instead of 10^9+7 when a!=b?

@rahul_g - in answer to your query,

It turns out that we get the same answer whenever n>1…

try the following test data and expected output which disproves your shortcut:


21 264 2
21 264 3
21 264 4
21 264 5



you simulated this?

@p____s in answer to your question

Why is everyone’s solution doing mod with (a-b) instead of 10^9+7 when a!=b?

For convenience let’s have c:=|a-b|.

Then either (1) we have c\mid a (and thus also c\mid b) and the answer is c, or (2) the process of finding GCD means that \gcd(a^n + b^n, c) = \gcd((a^n + b^n) \bmod c, c) = \gcd((a \bmod c)^n + (b \bmod c)^n, c).

And in fact (a\bmod c) = (b\bmod c) also means \gcd(a^n + b^n, c) = \gcd(2(a \bmod c)^n, c).

If c<1000000007, you don’t need to take a further modulus, but if that’s not be the case the GCD result can then be reduced to the answer modulus.

@rahul_g : conclusion, you got lucky with the test data.

Because GCD(A^N+B^N,A-B)=GCD((A^N+B^N)mod(A-B),A-B).

Python soulution:

from math import gcd
M = 10 ** 9 + 7
t = int(input())
for _ in range(t):
  a, b, n = map(int, input().split())
  m = a - b or M
  print(gcd(pow(a, n, m) + pow(b, n, m), a - b) % M)


can anyone tell the problem in this solution!

It’s multiplication overflow. Long long is not wide enough for product. Cast to __int128.

As @eugalt wrote, \text{gcd}(a,b) \,\text{mod}\,n has nothing to do with \text{gcd}(a\,\text{mod}\,n,b \,\text{mod}\,n), but however \text{gcd}(a,b) = \text{gcd}(a\,\text{mod}\,b,b).

Have a look at my "N independent " solution(except when a=b), of course it is wrong but it still passes . Test cases where it should have failed… some test cases :

  1. A=10, B=2, N=1 my answer=8(correct is 4)
  2. A=12, B=3,N=1 my answer=9(correct is 3)
  3. A=18,B=2,N>2
  4. A=22,B=6,N>2
  5. A=26,B=10,N>2

there are many many more test cases where it should have failed. Test cases were very weak. I understand that making good test cases is difficult task but this time they are extremely weak.

my solution

@beardaspirant Yupp. I did it for a, b, n <= 10.
But turns out this is not true in every case. I got really lucky with the test cases.