Count of numbers upto M with GCD equals to K when paired with M | Function to calculate GCD using euler totient function ; Finding the prime factors of limit to calculate it 's  euler totient function ; Calculating the euler totient function of ( mk ) ; Function print the count of numbers whose GCD with M equals to K ; GCD of m with any integer cannot be equal to k ; 0 and m itself will be the only valid integers ; Finding the number upto which coefficient of k can come ; Driver code
def EulerTotientFunction ( limit ) : NEW_LINE INDENT copy = limit NEW_LINE primes = [ ] NEW_LINE for i in range ( 2 , limit + 1 ) : NEW_LINE INDENT if i * i > limit : NEW_LINE INDENT break NEW_LINE DEDENT if ( limit % i == 0 ) : NEW_LINE INDENT while ( limit % i == 0 ) : NEW_LINE INDENT limit //= i NEW_LINE DEDENT primes . append ( i ) NEW_LINE DEDENT DEDENT if ( limit >= 2 ) : NEW_LINE INDENT primes . append ( limit ) NEW_LINE DEDENT ans = copy NEW_LINE for it in primes : NEW_LINE INDENT ans = ( ans // it ) * ( it - 1 ) NEW_LINE DEDENT return ans NEW_LINE DEDENT def CountGCD ( m , k ) : NEW_LINE INDENT if ( m % k != 0 ) : NEW_LINE INDENT print ( 0 ) NEW_LINE return NEW_LINE DEDENT if ( m == k ) : NEW_LINE INDENT print ( 2 ) NEW_LINE return NEW_LINE DEDENT limit = m // k NEW_LINE ans = EulerTotientFunction ( limit ) NEW_LINE print ( ans ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT M = 9 NEW_LINE K = 1 NEW_LINE CountGCD ( M , K ) NEW_LINE DEDENT