Recuento de números hasta M con GCD igual a K cuando se empareja con M

Dados dos enteros M y K , la tarea es contar el número de enteros entre [0, M] tales que MCD de ese entero con M es igual a K . 

Ejemplos: 

Entrada: M = 9, K = 1 
Salida: 6 
Explicación: 
Los números posibles tales que cuando se emparejan con 9, el GCD es 1, son 1, 2, 4, 5, 7, 8.

Entrada: M = 10, K = 5 
Salida: 1  

Acercarse:  

• Los enteros que tienen GCD K con M serán de la forma K, 2K, 3K, …..y así sucesivamente hasta M.
• Consideremos los coeficientes de K, es decir, 1, 2, 3, 4… hasta (M/K).
• Ahora solo tenemos que encontrar el número de esos coeficientes que tienen GCD con el número (M/K) = 1. Ahora el problema se reduce a encontrar el número de enteros entre 1 y (M/K) que tienen Gcd con (m/ k) = 1.
• Para encontrar esto usaremos la función totient de Euler de (M/K).

A continuación se muestra la implementación del enfoque anterior:  

// 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 function
int 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 K
void 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 code
int main()
{
 
    int M = 9;
    int K = 1;
    CountGCD(M, K);
 
    return 0;
}

// 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 function
static 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 K
static 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 code
public static void main(String[] args)
{
  
    int M = 9;
    int K = 1;
    CountGCD(M, K);
  
}
}
 
// This code is contributed by sapnasingh4991

# 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 function
def 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 K
def 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 code
if __name__ == '__main__':
 
    M = 9
    K = 1
    CountGCD(M, K)
 
# This code is contributed by mohit kumar 29   

// 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 function
static 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 K
static 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 code
public static void Main(String[] args)
{
    int M = 9;
    int K = 1;
    CountGCD(M, K);
}
}
 
// This code is contributed by PrinciRaj1992

<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 function
function 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 K
function 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>

6

Complejidad de tiempo: O((m/k) ^1/2 * log(m/k))

Espacio Auxiliar: O((m/k) ^1/2 )