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

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

# Time Complexity

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

--

--