The Coding Culture
Published in

The Coding Culture

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.

Solution:

Time Complexity

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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store