Photo by Joshua Aragon on Unsplash

Christmas Heist (Solution)

In this blog, we will look at how you could approach the problem “Christmas Heist” in The Coding Culture’s December Contest “Number Quest”.

Contest Page | CodeChef

Approach:

According to the Euclidean algorithm, for the given 2 integers

A and M where A > M then gcd( A, M ) = gcd( A-M, M ).

Similarly if (A+X) > M , then gcd( A+X , M ) = gcd( A+X-M , M ). Hence, we can say that we are looking at M integers X’ = (A+X) mod M, with 0 <= X’ < M and gcd( X’ , M ) = gcd( A , M ).

Hence, we need to find the number of X’ (0 <= X’ <= M) such that, gcd( X’ , M ) = gcd( A , M ).

Consider gcd( A , M ) = G. Hence, A = GA’ and M = GM’.

So, gcd( A , M ) = gcd( GA’ , GM’ ) = G. Therefore gcd( A’ , M’ ) = 1. Since gcd( X’ , M ) = gcd( A , M ) = G & considering X’= GX”, we can say that

gcd( X” , M’ ) = 1. Also since X’ is 0 <= X’ < M , then X” is 0 <= X” < M’.

So the answer to the problem is to calculate the number of X” in

0 <= X” < M’ which are co-prime with M’, which can be calculated using Euler’s Totient Function.

Solution:

Time Complexity

The Time Complexity for the factorization implementation of Euler’s Totient Function is O(√n).

Further Reading

Following is a link to a detailed explanation on Euler’s Totient Function:

Euler's totient function