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”.
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.
The Time Complexity for the factorization implementation of Euler’s Totient Function is O(√n).
Following is a link to a detailed explanation on Euler’s Totient Function: