GCDMOD - Editorial

editorial
, , , , ,
21

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

22

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:

23

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

24

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

25

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

26

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

27

Thanks @l_returns

28

Thanks for the test cases.

29

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

30

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

31

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