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

×

GCDMOD - Editorial

Problem Link

Practice

Contest

Author: Bhuvnesh Jain

Tester: Mark Mikhno

Editorialist: Bhuvnesh Jain

Difficulty

EASY-MEDIUM

Prerequisites

GCD, Modular Exponentiation, Overflow-handling

Problem

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

Explanation

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

$O(1)$

SOLUTIONS:

Author's solution can be found here.

Tester's solution can be found here.

mgch's solution can be found here.

This question is marked "community wiki".

asked 13 Aug, 15:07

likecs's gravatar image

6★likecs
3.7k1978
accept rate: 9%

edited 17 Aug, 10:51

l_returns's gravatar image

5★l_returns
1.2k19

4

Please fix this incomplete sentence - "The only property required to solve the complete problem is GCD(U,V)=GCD(U."

(14 Aug, 12:19) utkalsinha6★

edited that @utkalsinha but I am not sure whether it will really be edited or not as discuss is facing some issues nowadays...

(17 Aug, 10:52) l_returns5★

Thanks @l_returns

(19 Aug, 19:28) likecs6★

The links to the solutions are a bit mixed up. Currently, the solution marked as author solution is actually using int128.

(20 Aug, 11:32) ravibitsgoa4★

Can anyone explain me why we took

long long d = (bpow(a, n, a - b) + bpow(b, n, a - b)) % (a - b);

instead of

long long d = (bpow(a, n, MOD) + bpow(b, n, MOD)) % (MOD);

where mod is 10^9+7?

link

answered 14 Aug, 01:46

pallindromeguy's gravatar image

2★pallindromeguy
111
accept rate: 0%

You are referring to tester's solution. We are using the following identity: $GCD(A^N+B^N,A-B)=GCD((A^N+B^N)mod(A-B),A-B)$. Although the said solution does not output the result mod 10^9+7 which, I would think, it should.

(14 Aug, 04:30) eugalt3★

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

link

answered 14 Aug, 07:21

venturer's gravatar image

5★venturer
111
accept rate: 0%

Thanks for the test cases.

(19 Aug, 19:31) likecs6★

"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++ "

I was confused on this since day 1.

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

long long passed for me in C++, and I dont know why. And my friends got multiple WAs because of overflow, what is there in my approach that I avoided it in the step -

i=gcd; if((fastExpo((a%i),n,i)+fastExpo(b%i,n,i))%i==0)

link

answered 13 Aug, 15:16

vijju123's gravatar image

5★vijju123 ♦
14.8k11856
accept rate: 18%

I can't find anything like that in your code..
i.e. for a==b (var gcd==0 in your case)
your soln will exceed limits...
Weak test case or what ?

(13 Aug, 16:06) l_returns5★

THESE COMMENT I TRIED TO DELETE A LOT OF TIMES BUT IT WON'T ^^^^^

(13 Aug, 16:34) l_returns5★

i is integer and u assigned it a long long value !!
Soln should get WA but it doesn't
Maybe weak test case or some high maths which idk..

(13 Aug, 16:35) l_returns5★

Assume high level mathematics unless proven otherwise? :p XD

Though I feel it should get WA. I was surprised it didnt- even added an assert to check for overflow!

(14 Aug, 01:30) vijju123 ♦5★

Anyone who not got the editorial: A>B let y=A-B so A=y+B

now :A^n+B^n =(y+B)^n+B^n expand this y * (some value)+2 * B^n

since first part is already mutiple of y

Answer will be gcd of(y,2*B^n)

it can be done easily!!

link

answered 13 Aug, 15:26

khiljee's gravatar image

1★khiljee
192
accept rate: 0%

edited 13 Aug, 15:30

Answer doesn't depend on N except some special case like a=b or N=1 or N=2.If N>2 we can assume N=2 and answer will be same.I don't know why it gives correct answer. Due to weak test cases it passes even if don't use different approaches for N=1 and N>1. like for A=10,B=2, N=1 my solution gives answer 8 but correct answer is 4.similarly for A=12 , B=3 , N=1. my solution

link

answered 13 Aug, 15:44

venturer's gravatar image

5★venturer
111
accept rate: 0%

It's simple

gcd(a, b) = gcd(b, a % b)

Similarly

gcd(an + bn, a - b) is gcd(a - b, 2 * bn) since (an + bn) % (a - b) is 2 * bn. It can be seen very easily with polynomial division.

It's very simple to find now !!

This is my solution with prime factorization Solution

link

answered 13 Aug, 15:57

bvsbrk's gravatar image

2★bvsbrk
112
accept rate: 0%

edited 13 Aug, 15:58

@venturer - you say

Answer doesn't depend on N except some special case like a=b or N=1 or N=2.If N>2 we can assume N=2

but this is not correct. The follow test case would distinguish:

Input

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

Output

9
27
81
243


It's frustrating that there are two editorial threads for GCDMOD, can the mods amalgamate somehow? Or even just lock one of them?

link

answered 14 Aug, 04:45

joffan's gravatar image

4★joffan
6457
accept rate: 12%

There are discussions going in at least 2 of them - I cant delete them hence. I am seeing what can be done, if needed.

(14 Aug, 15:12) vijju123 ♦5★

Hello GCD(A+B,|A-B|)=GCD(AA+BB,|A-B|)=GCD(AAA+BBB,|A-B|) and so on...; therefore solution is GCD(A+B,|A-B|);

link

answered 14 Aug, 09:46

jawa2code's gravatar image

2★jawa2code
24127
accept rate: 0%

edited 14 Aug, 15:53

This is incorrect. GCD(2+1, |2-1|) != GCD(2 * 2 + 1 * 1, |2-1|)

(17 Aug, 00:55) rashomon4★

Can anyone explain me why my solution is giving tle and test cases where it fails

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

link

answered 14 Aug, 11:26

anshul1239's gravatar image

2★anshul1239
0
accept rate: 0%

As mentioned by @khiljee and @bvsbrk in the above posts, I used the fact that gcd(a^n + b^n, a-b) = gcd(2*b^n, a-b)


Use prime factorization to find GCD as below:
If we have the unique prime factorizations of a = p1^e1 p2^e2 ⋅⋅⋅ pm^em and b = p1^f1 p2^f2 ⋅⋅⋅ pm^fm where ei ≥ 0 and fi ≥ 0, then the gcd of a and b is gcd(a,b) = p1^min(e1,f1) * p2^min(e2,f2) * ⋅⋅⋅ pm^min(em,fm).*

I was failing some test cases while using the prime factorization approach as above. Which I fixed while the competition approached its end.

The case being, we can compute primes for 2*b and a-b separately and extend the solution to know primes for 2b^n, and hence find GCD. If you use 2b to compute prime, say 2 happened x times in prime factorization of 2*b, while extending the solution 2*b^n we should raise power as (x-1)*n + 1 instead of x*n times.

My solution here

link

answered 14 Aug, 15:41

nithinap's gravatar image

3★nithinap
11
accept rate: 0%

edited 14 Aug, 15:43

Can somebody tell me whats wrong in the following approach?

Let G be gcd(A^N+B^N, A-B) (assuming A > B)
We need to find G%M where M = 1e9+7.

G*X = A^N+B^N and G*Y = A-B take % on both sides
(G%M)*(X%M) = (A^N+B^N)%M and (G%M)*(Y%M) = (A-B)%M
Let G%M = G1, X%M = X1 and Y%M = Y1
G1*X1 = (A^N+B^N)%M
G1*Y1 = (A-B)%M
So from above two equations G1=G%M is gcd of (A^N+B^N)%M and (A-B)%M

Solution

link

answered 16 Aug, 00:45

shahanurag's gravatar image

4★shahanurag
11
accept rate: 0%

Hi @shahanurag, your assumption can be invalidated using the following:

GCD(A % M, B % M) != GCD(A, B) % M

Try it out for A = 14, B = 24 and M = 5:

GCD(14 % 5, 24 % 5) != GCD(14, 24) % 5
GCD(4, 4) != GCD(2) % 5
4 != 2 // which is true

I too got stuck at this point! But the following holds true:

GCD(A, B) = GCD(B, A % B)

So, we can say that:

GCD(AN+BN, A-B) = GCD(A-B, (AN+BN)%(A-B))

Thus while calculating (AN+BN)%M take M=A-B

and the answer would be GCD(M, (AN+BN)%M) % 1e9+7

Here's my solution

link

answered 16 Aug, 01:12

cherubim's gravatar image

3★cherubim
112
accept rate: 0%

edited 16 Aug, 16:23

Thank you, for a few days, I was stuck at this idea trying to prove or invalidate it. Finally I scrapped it, and now it turns out it was wrong. Thanks for giving a fail case :)

(16 Aug, 10:23) ruddradev2★

No problem mate. I'm glad that you found this helpful :)

(16 Aug, 13:47) cherubim3★

My solution was to notice that $A - B$ is smaller than $A ^ N + B ^ N$. Then we can find all the factors of $A - B$, and for each one of them check whether or not that factor of $A - B$ divides $A ^ N + B ^ N$ and by taking the maximum of all of these numbers we find the $gcd(A - B, A ^ N + B ^ N)$.

Time complexity - $O(TMlog N)$, $M = 10^6$

Solution - https://www.codechef.com/viewsolution/19438044

link

answered 16 Aug, 09:24

deepcpp's gravatar image

4★deepcpp
562
accept rate: 37%

Can't we use: long long d = (bpow(a, n, MOD) + bpow(b, n, MOD)) % (MOD);//MOD=10^9+7 instead of long long d = (bpow(a, n, a - b) + bpow(b, n, a - b)) % (a - b);

link

answered 17 Aug, 01:32

anixbreaker's gravatar image

2★anixbreaker
1
accept rate: 0%

Can anyone explain me the prod function in tester's solution,

long long prod(long long a, long long b, long long mod = MOD)
{
    long long res = 0;

    while(b)
    {
        if(b & 1)
            res = (res + a) % mod;
        a = (a + a) % mod;

        b >>= 1;       // right shift
    }

    return res;
}

I see it is similar to fast exponentiation but I don't really get this code

link

answered 25 Aug, 14:12

rainaswayam's gravatar image

2★rainaswayam
1
accept rate: 0%

Can anyone please explain me why first code https://www.codechef.com/viewsolution/21531950 gets TLE while the second one https://www.codechef.com/viewsolution/21531975 doesn't. The only difference between them is in loop condition. In first its (i*i)<=d while in second its i<=(d/i).

link

answered 08 Nov, 09:50

sparsh_garg's gravatar image

4★sparsh_garg
102
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,116
×1,602
×590
×304
×196
×152

question asked: 13 Aug, 15:07

question was seen: 4,330 times

last updated: 08 Nov, 09:55