Given two integers M and K, the task is to count the number of integers between [0, M] such that GCD of that integer with M equals K.
Examples:
Input: M = 9, K = 1
Output: 6
Explanation:
The possible numbers such that when paired with 9, there GCD is 1, are 1, 2, 4, 5, 7, 8.Input: M = 10, K = 5
Output: 1
Approach:
- Integers having GCD K with M will be of the form K, 2K, 3K, …..and so on up to M.
- Let’s consider the coefficients of K i.e 1, 2, 3, 4…up to (M/K).
- Now we just have to find the count of such coefficients which have GCD with the number (M/K) = 1. So now the problem reduces to find the number of integers between 1 to (M/K) having Gcd with (m/k) = 1.
- To find this we will use the Euler totient function of (M/K).
Below is the implementation of the above approach:
C++
// C++ program to Count of numbers// between 0 to M which have GCD// with M equals to K.#include <bits/stdc++.h>using namespace std;// Function to calculate GCD// using euler totient functionint EulerTotientFunction(int limit){ int copy = limit; // Finding the prime factors of // limit to calculate it's // euler totient function vector<int> primes; for (int i = 2; i * i <= limit; i++) { if (limit % i == 0) { while (limit % i == 0) { limit /= i; } primes.push_back(i); } } if (limit >= 2) { primes.push_back(limit); } // Calculating the euler totient // function of (m/k) int ans = copy; for (auto it : primes) { ans = (ans / it) * (it - 1); } return ans;}// Function print the count of// numbers whose GCD with M// equals to Kvoid CountGCD(int m, int k){ if (m % k != 0) { // GCD of m with any integer // cannot be equal to k cout << 0 << endl; return; } if (m == k) { // 0 and m itself will be // the only valid integers cout << 2 << endl; return; } // Finding the number upto which // coefficient of k can come int limit = m / k; int ans = EulerTotientFunction(limit); cout << ans << endl;}// Driver codeint main(){ int M = 9; int K = 1; CountGCD(M, K); return 0;} |
Java
// Java program to Count of numbers// between 0 to M which have GCD// with M equals to K.import java.util.*;class GFG{ // Function to calculate GCD// using euler totient functionstatic int EulerTotientFunction(int limit){ int copy = limit; // Finding the prime factors of // limit to calculate it's // euler totient function Vector<Integer> primes = new Vector<Integer>(); for (int i = 2; i * i <= limit; i++) { if (limit % i == 0) { while (limit % i == 0) { limit /= i; } primes.add(i); } } if (limit >= 2) { primes.add(limit); } // Calculating the euler totient // function of (m/k) int ans = copy; for (int it : primes) { ans = (ans / it) * (it - 1); } return ans;} // Function print the count of// numbers whose GCD with M// equals to Kstatic void CountGCD(int m, int k){ if (m % k != 0) { // GCD of m with any integer // cannot be equal to k System.out.print(0 +"\n"); return; } if (m == k) { // 0 and m itself will be // the only valid integers System.out.print(2 +"\n"); return; } // Finding the number upto which // coefficient of k can come int limit = m / k; int ans = EulerTotientFunction(limit); System.out.print(ans +"\n");}// Driver codepublic static void main(String[] args){ int M = 9; int K = 1; CountGCD(M, K); }}// This code is contributed by sapnasingh4991 |
Python3
# Python3 program to Count of numbers# between 0 to M which have GCD# with M equals to K.# Function to calculate GCD# using euler totient functiondef EulerTotientFunction(limit): copy = limit # Finding the prime factors of # limit to calculate it's # euler totient function primes = [] for i in range(2, limit + 1): if i * i > limit: break if (limit % i == 0): while (limit % i == 0): limit //= i primes.append(i) if (limit >= 2): primes.append(limit) # Calculating the euler totient # function of (m//k) ans = copy for it in primes: ans = (ans // it) * (it - 1) return ans# Function print the count of# numbers whose GCD with M# equals to Kdef CountGCD(m, k): if (m % k != 0): # GCD of m with any integer # cannot be equal to k print(0) return if (m == k): # 0 and m itself will be # the only valid integers print(2) return # Finding the number upto which # coefficient of k can come limit = m // k ans = EulerTotientFunction(limit) print(ans)# Driver codeif __name__ == '__main__': M = 9 K = 1 CountGCD(M, K)# This code is contributed by mohit kumar 29 |
C#
// C# program to Count of numbers// between 0 to M which have GCD// with M equals to K.using System;using System.Collections.Generic;class GFG{// Function to calculate GCD// using euler totient functionstatic int EulerTotientFunction(int limit){ int copy = limit; // Finding the prime factors of // limit to calculate it's // euler totient function List<int> primes = new List<int>(); for (int i = 2; i * i <= limit; i++) { if (limit % i == 0) { while (limit % i == 0) { limit /= i; } primes.Add(i); } } if (limit >= 2) { primes.Add(limit); } // Calculating the euler totient // function of (m/k) int ans = copy; foreach (int it in primes) { ans = (ans / it) * (it - 1); } return ans;}// Function print the count of// numbers whose GCD with M// equals to Kstatic void CountGCD(int m, int k){ if (m % k != 0) { // GCD of m with any integer // cannot be equal to k Console.Write(0 + "\n"); return; } if (m == k) { // 0 and m itself will be // the only valid integers Console.Write(2 + "\n"); return; } // Finding the number upto which // coefficient of k can come int limit = m / k; int ans = EulerTotientFunction(limit); Console.Write(ans + "\n");}// Driver codepublic static void Main(String[] args){ int M = 9; int K = 1; CountGCD(M, K);}}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// JavaScript program to Count of numbers// between 0 to M which have GCD// with M equals to K.// Function to calculate GCD// using euler totient functionfunction EulerTotientFunction(limit){ let copy = limit; // Finding the prime factors of // limit to calculate it's // euler totient function let primes = []; for (let i = 2; i * i <= limit; i++) { if (limit % i == 0) { while (limit % i == 0) { limit /= i; } primes.push(i); } } if (limit >= 2) { primes.push(limit); } // Calculating the euler totient // function of (m/k) let ans = copy; for (let it in primes) { ans = (ans / primes[it]) * (primes[it] - 1); } return ans;} // Function print the count of// numbers whose GCD with M// equals to Kfunction CountGCD(m, k){ if (m % k != 0) { // GCD of m with any integer // cannot be equal to k document.write(0 +"<br/>"); return; } if (m == k) { // 0 and m itself will be // the only valid integers document.write(2 +"<br/>"); return; } // Finding the number upto which // coefficient of k can come let limit = Math.floor(m / k); let ans = EulerTotientFunction(limit); document.write(ans +"\n");}// Driver Code let M = 9; let K = 1; CountGCD(M, K); </script> |
Output:
6
Time Complexity: O((m / k)1/2 * log(m/k))
Auxiliary Space: O((m / k)1/2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!