GCDMOD - Editorial

editorial
, , , , ,
8

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

9

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

3 Likes
10

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

1 Like
11

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);

1 Like
12

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

13

Can anyone please explain me why first code CodeChef: Practical coding for everyone gets TLE while the second one CodeChef: Practical coding for everyone doesn’t. The only difference between them is in loop condition. In first its (i*i)<=d while in second its i<=(d/i).

14

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.

1 Like
15

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

5 Likes
16

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

17

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 :slight_smile:

18

No problem mate. I’m glad that you found this helpful :slight_smile:

19

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

20

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

21

Thanks @l_returns

22

Thanks for the test cases.

23

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

24

long long d = (bpow(a, n, a - b) + bpow(b, n, a - b)) % (a - b)
Here why are we taking mod with (a-b) instead of 1e9+7 because a-b can be as big as 1e12 which is causing overflow but 1e9+7 won’t cause overflow. I am not able to understand where I am wrong.

25

my code is showing wrong answer even for the task 2 of sub-task 1.
plz. someone look into my code.

26

https://www.codechef.com/viewsolution/33210075
Can you please tell me what am I doing wrong in this code?

27

@waqar_ahmad224 Can you please check this?