Contar pares ordenados de números con un MCM dado

Dado un número entero N , la tarea es contar el número total de pares ordenados de modo que el MCM de cada par sea igual a N.

Ejemplos:

Entrada: N = 6
Salida: 9 
Explicación: 
Los pares con MCM igual a N(= 6) son {(1, 6), (2, 6), (2, 3), (3, 6), (6, 6) ), (6, 3), (3, 2), (6, 2), (6, 1)} 
Por lo tanto, la salida es 9.

Entrada: N = 36
Salida: 25

Enfoque: El problema se puede resolver con base en las siguientes observaciones:

Considere un par ordenado (X, Y). 
X = P ₁ ^a1 * P ₂ ^a2 * P ₃ ^a3 *…..* Pn ^an 
Y = P ₁ ^b1 * P ₂ ^b2 * P ₃ ^b3 *…..* Pn ^bn
Aquí, P ₁ , P ₂ , …. ., P _n son factores primos de X e Y. 
LCM(X, Y) = P ₁ ^{max(a1, b1)}  * P2 ^{max(a2, b2)} *……….*Pn ^{max(an, bn)}
Por lo tanto, mcm(x, y) = norte = pag ₁ ^{metro ₁} * pag ₂ ^{metro ₂} * pag₃ ^{m ₃} *…..* Pn ^{m _n}

Por lo tanto, el número total de pares ordenados (X, Y) 
= [{(m ₁ + 1) ² – m ₁ ² } * {(m ₂ + 1) ² – m ₂ ² } * ……* {(m _n + 1) ² – m _n ² } ]
= (2*m ₁ +1) * (2*m ₂ +1) * (2*m ₃ +1) * ……..* (2*m _n +1) .

Siga los pasos a continuación para resolver el problema:

1. Inicialice una variable, digamos, countPower , para almacenar la potencia de todos los factores primos de N .
2. Calcular la potencia de todos los factores primos de N .
3. Finalmente, imprima el conteo de pares ordenados (X, Y) usando la fórmula mencionada anteriormente.

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

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the number of
// ordered pairs with given LCM
int CtOrderedPairs(int N)
{
    // Stores count of
    // ordered pairs
    int res = 1;
 
    // Calculate power of all
    // prime factors of N
    for (int i = 2; i * i <= N; i++) {
 
        // Store the power of
        // prime factors
        int countPower = 0;
        while (N % i == 0) {
            countPower++;
            N /= i;
        }
 
        res = res * (2 * countPower
                     + 1);
    }
 
    if (N > 1) {
        res = res * (2 * 1 + 1);
    }
    return res;
}
 
// Driver Code
int main()
{
    int N = 36;
    cout << CtOrderedPairs(N);
}

// Java program to implement
// the above approach
 
class GFG{
   
// Function to count the number of
// ordered pairs with given LCM
static int CtOrderedPairs(int N)
{
     
    // Stores count of
    // ordered pairs
    int res = 1;
 
    // Calculate power of all
    // prime factors of N
    for(int i = 2; i * i <= N; i++)
    {
         
        // Store the power of
        // prime factors
        int countPower = 0;
         
        while (N % i == 0)
        {
            countPower++;
            N /= i;
        }
        res = res * (2 * countPower + 1);
    }
 
    if (N > 1)
    {
        res = res * (2 * 1 + 1);
    }
    return res;
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 36;
     
    System.out.println(CtOrderedPairs(N));
}
}
 
// This code is contributed by aimformohan

# Python3 program to implement
# the above approach
  
# Function to count the number of
# ordered pairs with given LCM
def CtOrderedPairs(N):
 
    # Stores count of
    # ordered pairs
    res = 1
  
    # Calculate power of all
    # prime factors of N
    i = 2
    while(i * i <= N):
  
        # Store the power of
        # prime factors
        countPower = 0
        while (N % i == 0):
            countPower += 1
            N //= i
  
        res = res * (2 * countPower + 1)
        i += 1
     
    if (N > 1):
        res = res * (2 * 1 + 1)
     
    return res
 
# Driver Code
N = 36
 
print(CtOrderedPairs(N))
 
# This code is contributed by code_hunt

// C# program to implement
// the above approach
using System;
  
class GFG{
    
// Function to count the number of
// ordered pairs with given LCM
static int CtOrderedPairs(int N)
{
     
    // Stores count of
    // ordered pairs
    int res = 1;
  
    // Calculate power of all
    // prime factors of N
    for(int i = 2; i * i <= N; i++)
    {
          
        // Store the power of
        // prime factors
        int countPower = 0;
          
        while (N % i == 0)
        {
            countPower++;
            N /= i;
        }
        res = res * (2 * countPower + 1);
    }
  
    if (N > 1)
    {
        res = res * (2 * 1 + 1);
    }
    return res;
}
  
// Driver Code
public static void Main()
{
    int N = 36;
      
    Console.WriteLine(CtOrderedPairs(N));
}
}
 
// This code is contributed by code_hunt

<script>
 
// Javascript program to implement
// the above approach
 
// Function to count the number of
// ordered pairs with given LCM
function CtOrderedPairs(N)
{
       
    // Stores count of
    // ordered pairs
    let res = 1;
   
    // Calculate power of all
    // prime factors of N
    for(let i = 2; i * i <= N; i++)
    {
           
        // Store the power of
        // prime factors
        let countPower = 0;
           
        while (N % i == 0)
        {
            countPower++;
            N /= i;
        }
        res = res * (2 * countPower + 1);
    }
   
    if (N > 1)
    {
        res = res * (2 * 1 + 1);
    }
    return res;
}
 
// Driver Code
 
    let N = 36;
       
    document.write(CtOrderedPairs(N));
           
</script>

25

Complejidad de Tiempo: O(√N)  
Espacio Auxiliar: O(1)