GCD máximo del producto dado de incógnitas

Dados dos enteros N y P donde P es el producto de N enteros desconocidos, la tarea es encontrar el MCD de esos enteros. Puede haber diferentes grupos de enteros posibles que den el mismo producto, en ese caso, imprima el MCD que es el máximo entre todos los grupos posibles.
Ejemplos: 
 

Entrada: N = 3, P = 24 
Salida: 2 
{1, 1, 24}, {1, 2, 12}, {1, 3, 8}, {1, 4, 6}, {2, 2, 6 } y {2, 3, 4} 
son los únicos grupos de enteros posibles con producto = 24 
y tienen GCD 1, 1, 1, 1, 2 y 1 respectivamente.
Entrada: N = 5, P = 1 
Salida: 
 

Enfoque: Sea g el mcd de a ₁ , a ₂ , a ₃ , …, a _n . Ya que, a _i debe ser múltiplo de g para cada i y su producto P = a ₁ * a ₂ * a ₃ * … * a _n debe ser múltiplo de g ⁿ . La respuesta es el g máximo tal que g ⁿ % P = 0 . 
Sea P = k ₁ ^{p ₁} * k ₂ ^{p ₂}* k ₃ ^{pag ₃} * … * k _norte ^{pag _.} Entonces g debe ser de la forma k ₁ ^{p ₁ ‘} * k ₂ ^{p ₂ ‘} * k ₃ ^{p _3′} * … * k _n ^{p _t ‘} . Para maximizar g debemos elegir p _i ^‘ = p _i / N
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to return the required gcd
long max_gcd(long n, long p)
{
    int count = 0;
    long gcd = 1;
 
    // Count the number of times 2 divides p
    while (p % 2 == 0)
    {
 
        // Equivalent to p = p / 2;
        p >>= 1;
        count++;
    }
 
    // If 2 divides p
    if (count > 0)
        gcd *= (long)pow(2, count / n);
 
    // Check all the possible numbers
    // that can divide p
    for (long i = 3; i <= sqrt(p); i += 2)
    {
        count = 0;
        while (p % i == 0)
        {
            count++;
            p = p / i;
        }
        if (count > 0)
        {
            gcd *= (long)pow(i, count / n);
        }
    }
 
    // If n in the end is a prime number
    if (p > 2)
        gcd *= (long)pow(p, 1 / n);
 
    // Return the required gcd
    return gcd;
}
 
// Driver code
int main()
{
    long n = 3;
    long p = 80;
    cout << max_gcd(n, p);
}
     
// This code is contributed by Code_Mech

// Java implementation of the approach
class GFG {
 
    // Function to return the required gcd
    static long max_gcd(long n, long p)
    {
        int count = 0;
        long gcd = 1;
 
        // Count the number of times 2 divides p
        while (p % 2 == 0) {
 
            // Equivalent to p = p / 2;
            p >>= 1;
            count++;
        }
 
        // If 2 divides p
        if (count > 0)
            gcd *= (long)Math.pow(2, count / n);
 
        // Check all the possible numbers
        // that can divide p
        for (long i = 3; i <= Math.sqrt(p); i += 2) {
            count = 0;
            while (p % i == 0) {
                count++;
                p = p / i;
            }
            if (count > 0) {
                gcd *= (long)Math.pow(i, count / n);
            }
        }
 
        // If n in the end is a prime number
        if (p > 2)
            gcd *= (long)Math.pow(p, 1 / n);
 
        // Return the required gcd
        return gcd;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        long n = 3;
        long p = 80;
        System.out.println(max_gcd(n, p));
    }
}

# Python3 implementation of the approach
import math
 
# Function to return the required gcd
def max_gcd(n, p):
 
    count = 0;
    gcd = 1;
 
    # Count the number of times 2 divides p
    while (p % 2 == 0):
     
        # Equivalent to p = p / 2;
        p >>= 1;
        count = count + 1;
     
    # If 2 divides p
    if (count > 0):
        gcd = gcd * pow(2, count // n);
 
    # Check all the possible numbers
    # that can divide p
    for i in range(3, (int)(math.sqrt(p)), 2):
     
        count = 0;
        while (p % i == 0):
         
            count = count + 1;
            p = p // i;
         
        if (count > 0):
         
            gcd = gcd * pow(i, count // n);
         
    # If n in the end is a prime number
    if (p > 2) :
        gcd = gcd * pow(p, 1 // n);
 
    # Return the required gcd
    return gcd;
 
# Driver code
n = 3;
p = 80;
print(max_gcd(n, p));
 
# This code is contributed by Shivi_Aggarwal

// C# implementation of the approach
using System;
 
class GFG
{
 
// Function to return the required gcd
static long max_gcd(long n, long p)
{
    int count = 0;
    long gcd = 1;
 
    // Count the number of times 2 divides p
    while (p % 2 == 0)
    {
 
        // Equivalent to p = p / 2;
        p >>= 1;
        count++;
    }
 
    // If 2 divides p
    if (count > 0)
        gcd *= (long)Math.Pow(2, count / n);
 
    // Check all the possible numbers
    // that can divide p
    for (long i = 3; i <= Math.Sqrt(p); i += 2)
    {
        count = 0;
        while (p % i == 0)
        {
            count++;
            p = p / i;
        }
        if (count > 0)
        {
            gcd *= (long)Math.Pow(i, count / n);
        }
    }
 
    // If n in the end is a prime number
    if (p > 2)
        gcd *= (long)Math.Pow(p, 1 / n);
 
    // Return the required gcd
    return gcd;
}
 
// Driver code
public static void Main()
{
    long n = 3;
    long p = 80;
    Console.WriteLine(max_gcd(n, p));
}
}
 
// This code is contributed by Ryuga

<?php
// PHP implementation of the approach
 
// Function to return the required gcd
function max_gcd($n, $p)
{
    $count = 0;
    $gcd = 1;
 
    // Count the number of times 2 divides p
    while ($p % 2 == 0)
    {
 
        // Equivalent to p = p / 2;
        $p >>= 1;
        $count++;
    }
 
    // If 2 divides p
    if ($count > 0)
        $gcd *= pow(2, (int)($count / $n));
 
    // Check all the possible numbers
    // that can divide p
    for ($i = 3; $i <= (int)sqrt($p); $i += 2)
    {
        $count = 0;
        while ($p % $i == 0)
        {
            $count++;
            $p = (int)($p / $i);
        }
        if ($count > 0)
        {
            $gcd *= pow($i, (int)($count / $n));
        }
    }
 
    // If n in the end is a prime number
    if ($p > 2)
        $gcd *= pow($p, (int)(1 / $n));
 
    // Return the required gcd
    return $gcd;
}
 
// Driver code
$n = 3;
$p = 80;
echo(max_gcd($n, $p));
 
// This code is contributed by Code_Mech

<script>
    // Javascript implementation of the approach
     
    // Function to return the required gcd
    function max_gcd(n, p)
    {
        let count = 0;
        let gcd = 1;
 
        // Count the number of times 2 divides p
        while (p % 2 == 0)
        {
 
            // Equivalent to p = p / 2;
            p >>= 1;
            count++;
        }
 
        // If 2 divides p
        if (count > 0)
            gcd *= Math.pow(2, parseInt(count / n, 10));
 
        // Check all the possible numbers
        // that can divide p
        for (let i = 3; i <= parseInt(Math.sqrt(p), 10); i += 2)
        {
            count = 0;
            while (p % i == 0)
            {
                count++;
                p = parseInt(p / i, 10);
            }
            if (count > 0)
            {
                gcd *= Math.pow(i, parseInt(count / n, 10));
            }
        }
 
        // If n in the end is a prime number
        if (p > 2)
            gcd *= Math.pow(p, parseInt(1 / n, 10));
 
        // Return the required gcd
        return gcd;
    }
     
    let n = 3;
    let p = 80;
    document.write(max_gcd(n, p));
     
</script>

2

Complejidad de tiempo: O(sqrtp*logn)

Espacio Auxiliar: O(1)