# 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

**, with**

*X’ = (A+X) mod M***and**

*0 <= X’ < M***.**

*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,

**and**

*A = GA’*

*M = GM’.*So, ** gcd( A , M ) = gcd( GA’ , GM’ )** = G. Therefore

**. Since**

*gcd( A’ , M’ ) = 1***& considering**

*gcd( X’ , M ) = gcd( A , M ) = G***, we can say that**

*X’= GX”*** gcd( X” , M’ ) = 1**. Also since

**is**

*X’*

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