Minimice los pasos necesarios para igualar dos valores mediante la división repetida por cualquiera de sus factores primos que sea menor que M

Dados tres enteros positivos M , X e Y , la tarea es encontrar el número mínimo de operaciones requeridas para hacer que X e Y sean iguales de modo que en cada operación se divida X o Y por uno de sus factores primos menor que M . Si no es posible hacer que X e Y sean iguales, imprima «-1» .

Ejemplos:

Entrada: X = 20, Y =16, M = 10
Salida: 3
Explicación:
Realice la operación en X e Y como se ilustra a continuación:
X: 20 -> 4 : 20/5 = 4
Y: 16 -> 8 : 16/ 2 = 8, 8 -> 4 : 8/2 = 4
Por lo tanto, el número total de pasos necesarios para hacer que X e Y sean iguales es 3.

Entrada: X = 160, Y = 180, M = 10
Salida: 5

Enfoque: La idea para resolver el problema dado se basa en la observación de que el valor en el que tanto X como Y son iguales es el MCD de X e Y. Siga los pasos a continuación para resolver el problema:

Calcule previamente todos los factores primos de los números hasta 10 ⁶ usando la criba de Eratóstenes y guárdelos en una array.
Calcule el MCD de los números X e Y y almacene su valor en una variable, digamos MCD .
Ahora, cuenta el número de factores primos en X/GCD e Y/GCD . Si cualquier factor primo tiene un valor mayor que M , entonces no es posible hacer que X e Y sean iguales. Por lo tanto, imprima “-1” .
De lo contrario, imprima la suma de números primos en X / GCD e Y / GCD como resultado.

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

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Stores the prime factor of numbers
int primes[1000006];
 
// Function to find GCD of a and b
int gcd(int a, int b)
{
     
    // Base Case
    if (b == 0)
        return a;
 
    // Otherwise, calculate GCD
    else
        return gcd(b, a % b);
}
 
// Function to precompute the
// prime numbers till 1000000
void preprocess()
{
     
    // Initialize all the positions
    // with their respective values
    for(int i = 1; i <= 1000000; i++)
        primes[i] = i;
 
    // Iterate over the range [2, sqrt(10^6)]
    for(int i = 2; i * i <= 1000000; i++)
    {
         
        // If i is prime number
        if (primes[i] == i)
        {
             
            // Mark it as the factor
            for(int j = 2 * i; j <= 1000000; j += i)
            {
                if (primes[j] == j)
                    primes[j] = i;
            }
        }
    }
}
 
// Utility function to count the number
// of steps to make X and Y equal
int Steps(int x, int m)
{
     
    // Initialise steps
    int steps = 0;
 
    bool flag = false;
 
    // Iterate x is at most 1
    while (x > 1)
    {
        if (primes[x] > m)
        {
            flag = true;
            break;
        }
 
        // Divide with the
        // smallest prime factor
        x /= primes[x];
 
        steps++;
    }
 
    // If X and Y can't be
    // made equal
    if (flag)
        return -1;
 
    // Return steps
    return steps;
}
 
// Function to find the minimum number of
// steps required to make X and Y equal
int minimumSteps(int x, int y, int m)
{
     
    // Generate all the prime factors
    preprocess();
 
    // Calculate GCD of x and y
    int g = gcd(x, y);
 
    // Divide the numbers by their gcd
    x = x / g;
    y = y / g;
 
    int x_steps = Steps(x, m);
    int y_steps = Steps(y, m);
 
    // If not possible, then return -1;
    if (x_steps == -1 || y_steps == -1)
        return -1;
 
    // Return the resultant number of steps
    return x_steps + y_steps;
}
 
// Driver Code
int main()
{
    int X = 160;
    int Y = 180;
    int M = 10;
 
    cout << (minimumSteps(X, Y, M));
}
 
// This code is contributed by chitranayal

Java

// Java program for the above approach
import java.util.*;
 
public class GFG {
 
    // Stores the prime factor of numbers
    static int primes[] = new int[1000006];
 
    // Function to find GCD of a and b
    static int gcd(int a, int b)
    {
        // Base Case
        if (b == 0)
            return a;
 
        // Otherwise, calculate GCD
        else
            return gcd(b, a % b);
    }
 
    // Function to precompute the
    // prime numbers till 1000000
    static void preprocess()
    {
        // Initialize all the positions
        // with their respective values
        for (int i = 1; i <= 1000000; i++)
            primes[i] = i;
 
        // Iterate over the range [2, sqrt(10^6)]
        for (int i = 2; i * i <= 1000000; i++) {
 
            // If i is prime number
            if (primes[i] == i) {
 
                // Mark it as the factor
                for (int j = 2 * i;
                     j <= 1000000; j += i) {
 
                    if (primes[j] == j)
                        primes[j] = i;
                }
            }
        }
    }
 
    // Utility function to count the number
    // of steps to make X and Y equal
    static int Steps(int x, int m)
    {
        // Initialise steps
        int steps = 0;
 
        boolean flag = false;
 
        // Iterate x is at most 1
        while (x > 1) {
            if (primes[x] > m) {
                flag = true;
                break;
            }
 
            // Divide with the
            // smallest prime factor
            x /= primes[x];
 
            steps++;
        }
 
        // If X and Y can't be
        // made equal
        if (flag)
            return -1;
 
        // Return steps
        return steps;
    }
 
    // Function to find the minimum number of
    // steps required to make X and Y equal
    static int minimumSteps(int x, int y, int m)
    {
        // Generate all the prime factors
        preprocess();
 
        // Calculate GCD of x and y
        int g = gcd(x, y);
 
        // Divide the numbers by their gcd
        x = x / g;
        y = y / g;
 
        int x_steps = Steps(x, m);
        int y_steps = Steps(y, m);
 
        // If not possible, then return -1;
        if (x_steps == -1 || y_steps == -1)
            return -1;
 
        // Return the resultant number of steps
        return x_steps + y_steps;
    }
 
    // Driver Code
    public static void main(String args[])
    {
        int X = 160;
        int Y = 180;
        int M = 10;
 
        System.out.println(
            minimumSteps(X, Y, M));
    }
}

Python3

# Python program for the above approach
 
# Stores the prime factor of numbers
primes = [0] * (1000006)
 
# Function to find GCD of a and b
def gcd(a, b) :
     
    # Base Case
    if (b == 0) :
        return a
 
    # Otherwise, calculate GCD
    else :
        return gcd(b, a % b)
 
 
# Function to precompute the
# prime numbers till 1000000
def preprocess() :
     
    # Initialize all the positions
    # with their respective values
    for i in range(1, 1000001):
        primes[i] = i
 
    # Iterate over the range [2, sqrt(10^6)]
    i = 2
    while(i * i <= 1000000)  :
         
        # If i is prime number
        if (primes[i] == i) :
             
            # Mark it as the factor
            for j in range(2 * i, 1000001, i):
                if (primes[j] == j) :
                    primes[j] = i     
        i += 1
 
# Utility function to count the number
# of steps to make X and Y equal
def Steps(x, m) :
     
    # Initialise steps
    steps = 0
 
    flag = False
 
    # Iterate x is at most 1
    while (x > 1) :
         
        if (primes[x] > m) :
            flag = True
            break
         
 
        # Divide with the
        # smallest prime factor
        x //= primes[x]
 
        steps += 1
     
 
    # If X and Y can't be
    # made equal
    if (flag != 0) :
        return -1
 
    # Return steps
    return steps
 
 
# Function to find the minimum number of
# steps required to make X and Y equal
def minimumSteps(x, y, m) :
     
    # Generate all the prime factors
    preprocess()
 
    # Calculate GCD of x and y
    g = gcd(x, y)
 
    # Divide the numbers by their gcd
    x = x // g
    y = y // g
 
    x_steps = Steps(x, m)
    y_steps = Steps(y, m)
 
    # If not possible, then return -1
    if (x_steps == -1 or y_steps == -1) :
        return -1
 
    # Return the resultant number of steps
    return x_steps + y_steps
 
 
# Driver Code
X = 160
Y = 180
M = 10
 
print(minimumSteps(X, Y, M))
 
# This code is contributed by souravghosh0416.

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Stores the prime factor of numbers
static int[] primes = new int[1000006];
 
// Function to find GCD of a and b
static int gcd(int a, int b)
{
     
    // Base Case
    if (b == 0)
        return a;
     
    // Otherwise, calculate GCD
    else
        return gcd(b, a % b);
}
 
// Function to precompute the
// prime numbers till 1000000
static void preprocess()
{
     
    // Initialize all the positions
    // with their respective values
    for(int i = 1; i <= 1000000; i++)
        primes[i] = i;
     
    // Iterate over the range [2, sqrt(10^6)]
    for(int i = 2; i * i <= 1000000; i++)
    {
         
        // If i is prime number
        if (primes[i] == i)
        {
             
            // Mark it as the factor
            for(int j = 2 * i;
                    j <= 1000000; j += i)
            {
                if (primes[j] == j)
                    primes[j] = i;
            }
        }
    }
}
 
// Utility function to count the number
// of steps to make X and Y equal
static int Steps(int x, int m)
{
     
    // Initialise steps
    int steps = 0;
     
    bool flag = false;
     
    // Iterate x is at most 1
    while (x > 1)
    {
        if (primes[x] > m)
        {
            flag = true;
            break;
        }
         
        // Divide with the
        // smallest prime factor
        x /= primes[x];
         
        steps++;
    }
     
    // If X and Y can't be
    // made equal
    if (flag)
        return -1;
     
    // Return steps
    return steps;
}
 
// Function to find the minimum number of
// steps required to make X and Y equal
static int minimumSteps(int x, int y, int m)
{
     
    // Generate all the prime factors
    preprocess();
     
    // Calculate GCD of x and y
    int g = gcd(x, y);
     
    // Divide the numbers by their gcd
    x = x / g;
    y = y / g;
     
    int x_steps = Steps(x, m);
    int y_steps = Steps(y, m);
     
    // If not possible, then return -1;
    if (x_steps == -1 || y_steps == -1)
        return -1;
     
    // Return the resultant number of steps
    return x_steps + y_steps;
}
 
// Driver code
static void Main()
{
    int X = 160;
    int Y = 180;
    int M = 10;
     
    Console.Write(minimumSteps(X, Y, M));
}
}
 
// This code is contributed by sanjoy_62

Javascript

<script>
 
// Javascript program for the above approach
 
    // Stores the prime factor of numbers
    var primes = Array(1000006).fill(0);
 
    // Function to find GCD of a and b
    function gcd(a , b) {
        // Base Case
        if (b == 0)
            return a;
 
        // Otherwise, calculate GCD
        else
            return gcd(b, a % b);
    }
 
    // Function to precompute the
    // prime numbers till 1000000
    function preprocess() {
        // Initialize all the positions
        // with their respective values
        for (i = 1; i <= 1000000; i++)
            primes[i] = i;
 
        // Iterate over the range [2, sqrt(10^6)]
        for (i = 2; i * i <= 1000000; i++) {
 
            // If i is prime number
            if (primes[i] == i) {
 
                // Mark it as the factor
                for (j = 2 * i; j <= 1000000; j += i) {
 
                    if (primes[j] == j)
                        primes[j] = i;
                }
            }
        }
    }
 
    // Utility function to count the number
    // of steps to make X and Y equal
    function Steps(x , m) {
        // Initialise steps
        var steps = 0;
 
        var flag = false;
 
        // Iterate x is at most 1
        while (x > 1) {
            if (primes[x] > m) {
                flag = true;
                break;
            }
 
            // Divide with the
            // smallest prime factor
            x /= primes[x];
 
            steps++;
        }
 
        // If X and Y can't be
        // made equal
        if (flag)
            return -1;
 
        // Return steps
        return steps;
    }
 
    // Function to find the minimum number of
    // steps required to make X and Y equal
    function minimumSteps(x , y , m) {
        // Generate all the prime factors
        preprocess();
 
        // Calculate GCD of x and y
        var g = gcd(x, y);
 
        // Divide the numbers by their gcd
        x = x / g;
        y = y / g;
 
        var x_steps = Steps(x, m);
        var y_steps = Steps(y, m);
 
        // If not possible, then return -1;
        if (x_steps == -1 || y_steps == -1)
            return -1;
 
        // Return the resultant number of steps
        return x_steps + y_steps;
    }
 
    // Driver Code
     
        var X = 160;
        var Y = 180;
        var M = 10;
 
        document.write(minimumSteps(X, Y, M));
 
// This code contributed by umadevi9616
 
</script>

Producción:

Complejidad temporal: O(N log N)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por hemanthswarna1506 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta