Dados dos números X e Y , la tarea es hacer que ambos sean iguales multiplicando repetidamente con sus factores primos el número mínimo de veces.
Ejemplos:
Entrada: X = 36, Y = 48
Salida: 3
Explicación:
Operación 1: Elija 2 (factor primo de X) y multiplique con X. Ahora, X = 72, Y = 48.
Operación 2: Elija 2 (factor primo de X ) y multiplique con X, Ahora, X = 144, Y = 48
Operación 3: Elija 3 (factor primo de Y) y multiplique con X. Ahora, X = 144, Y = 144Entrada: X = 10, Y = 14
Salida: -1
Enfoque: La idea es que X e Y pueden hacerse iguales solo si todo factor primo de X está presente en Y y todo factor primo de Y está presente en X. Para contar las operaciones mínimas requeridas para igualarlos, siga los siguientes pasos:
- Calcule el mcd de X e Y , digamos MCD y encuentre newX = X/GCD y newY = Y/GCD para eliminar los factores primos comunes .
- Encuentre los factores primos con sus frecuencias de newX y newY .
- Compruebe que cada factor primo de newX esté presente en Y( dividirá Y) y que cada factor primo de newY esté presente en X( dividirá X) . Si no , devuelve -1.
- Inicialice una variable, digamos ans =0, para almacenar la cantidad de operaciones requeridas.
- Agregue todas las frecuencias de los números primos de newX y newY al ans .
- Devuelve la respuesta .
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;
// Function to calculate total number of
// prime factor with their prime factor
unordered_map<int, int> PrimeFactor(int N)
{
unordered_map<int, int> primef;
// Iterate while the number is even
while (N % 2 == 0)
{
if (primef.count(2))
{
primef[2] += 1;
}
else
{
primef[2] = 1;
}
// Reduce to half
N /= 2;
}
// Iterate up to sqrt(N)
for(int i = 3; i <= sqrt(N); i++)
{
// Iterate while N has
// factors of i
while (N % i == 0)
{
if (primef.count(i))
{
primef[i] += 1;
}
else
{
primef[i] = 1;
}
// Removing one factor of i
N /= 2;
}
}
if (N > 2)
{
primef[N] = 1;
}
return primef;
}
// Function to count the number of factors
int CountToMakeEqual(int X, int Y)
{
// Find the GCD
int gcdofXY = __gcd(X, Y);
// Find multiples left in X and Y
int newX = Y / gcdofXY;
int newY = X / gcdofXY;
// Find prime factor of multiple
// left in X and Y
unordered_map<int, int> primeX;
unordered_map<int, int> primeY;
primeX = PrimeFactor(newX);
primeY = PrimeFactor(newY);
// Initialize ans
int ans = 0;
// Check if it possible
// to obtain X or not
for(auto c : primeX)
{
if (X % c.first != 0)
{
return -1;
}
ans += primeX[c.first];
}
// Check if it possible to
// obtain Y or not
for(auto c : primeY)
{
if (Y % c.first != 0)
{
return -1;
}
ans += primeY[c.first];
}
// return main ans
return ans;
}
// Driver code
int main()
{
// Given Input
int X = 36;
int Y = 48;
// Function Call
int ans = CountToMakeEqual(X, Y);
cout << ans << endl;
return 0;
}
// This code is contributed by adarshsinghk
Java
// Java program for the above approach
import java.util.*;
public class Main
{
static int gcd(int a, int b)
{
// Everything divides 0
if (b == 0)
{
return a;
}
return gcd(b, a % b);
}
// Function to calculate total number of
// prime factor with their prime factor
static HashMap<Integer, Integer> PrimeFactor(int N)
{
HashMap<Integer, Integer> primef = new HashMap<Integer, Integer>();
// Iterate while the number is even
while (N % 2 == 0)
{
if (primef.containsKey(2))
{
primef.put(2, primef.get(2) + 1);
}
else
{
primef.put(2, 1);
}
// Reduce to half
N = N / 2;
}
// Iterate up to sqrt(N)
for(int i = 3; i <= Math.sqrt(N); i++)
{
// Iterate while N has
// factors of i
while (N % i == 0)
{
if (primef.containsKey(i))
{
primef.put(i, primef.get(i) + 1);
}
else
{
primef.put(i, 1);
}
// Removing one factor of i
N = N / 2;
}
}
if (N > 2)
{
primef.put(N, 1);
}
return primef;
}
// Function to count the number of factors
static int CountToMakeEqual(int X, int Y)
{
// Find the GCD
int gcdofXY = gcd(X, Y);
// Find multiples left in X and Y
int newX = Y / gcdofXY;
int newY = X / gcdofXY;
// Find prime factor of multiple
// left in X and Y
HashMap<Integer, Integer> primeX = PrimeFactor(newX);
HashMap<Integer, Integer> primeY = PrimeFactor(newY);
// Initialize ans
int ans = 0;
// Check if it possible
// to obtain X or not
for (Map.Entry keys : primeX.entrySet()) {
if (X % (int)keys.getKey() != 0)
{
return -1;
}
ans += primeX.get(keys.getKey());
}
// Check if it possible to
// obtain Y or not
for (Map.Entry keys : primeY.entrySet()) {
if (Y % (int)keys.getKey() != 0)
{
return -1;
}
ans += primeY.get(keys.getKey());
}
// Return main ans
return ans;
}
public static void main(String[] args) {
// Given Input
int X = 36;
int Y = 48;
// Function Call
int ans = CountToMakeEqual(X, Y);
System.out.println(ans);
}
}
// This code is contributed by mukesh07.
Python3
# Python program for the above approach import math # Function to calculate total number of # prime factor with their prime factor def PrimeFactor(N): ANS = dict() # Iterate while the number is even while N % 2 == 0: if 2 in ANS: ANS[2] += 1 else: ANS[2] = 1 # Reduce to half N = N//2 # Iterate up to sqrt(N) for i in range(3, int(math.sqrt(N))+1, 2): # Iterate while N has # factors of i while N % i == 0: if i in ANS: ANS[i] += 1 else: ANS[i] = 1 # Removing one factor of i N = N // i if 2 < N: ANS[N] = 1 return ANS # Function to count the number of factors def CountToMakeEqual(X, Y): # Find the GCD GCD = math.gcd(X, Y) # Find multiples left in X and Y newY = X//GCD newX = Y//GCD # Find prime factor of multiple # left in X and Y primeX = PrimeFactor(newX) primeY = PrimeFactor(newY) # Initialize ans ans = 0 # Check if it possible # to obtain X or not for factor in primeX: if X % factor != 0: return -1 ans += primeX[factor] # Check if it possible to # obtain Y or not for factor in primeY: if Y % factor != 0: return -1 ans += primeY[factor] # return main ans return ans # Driver Code if __name__ == "__main__": # Given Input X = 36 Y = 48 # Function Call ans = CountToMakeEqual(X, Y) print(ans)
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
static int gcd(int a, int b)
{
// Everything divides 0
if (b == 0)
{
return a;
}
return gcd(b, a % b);
}
// Function to calculate total number of
// prime factor with their prime factor
static Dictionary<int, int> PrimeFactor(int N)
{
Dictionary<int,
int> primef = new Dictionary<int,
int>();
// Iterate while the number is even
while (N % 2 == 0)
{
if (primef.ContainsKey(2))
{
primef[2]++;
}
else
{
primef[2] = 1;
}
// Reduce to half
N = N / 2;
}
// Iterate up to sqrt(N)
for(int i = 3; i <= Math.Sqrt(N); i++)
{
// Iterate while N has
// factors of i
while (N % i == 0)
{
if (primef.ContainsKey(i))
{
primef[i]++;
}
else
{
primef[i] = 1;
}
// Removing one factor of i
N = N / 2;
}
}
if (N > 2)
{
primef[N] = 1;
}
return primef;
}
// Function to count the number of factors
static int CountToMakeEqual(int X, int Y)
{
// Find the GCD
int gcdofXY = gcd(X, Y);
// Find multiples left in X and Y
int newX = Y / gcdofXY;
int newY = X / gcdofXY;
// Find prime factor of multiple
// left in X and Y
Dictionary<int, int> primeX = PrimeFactor(newX);
Dictionary<int, int> primeY = PrimeFactor(newY);
// Initialize ans
int ans = 0;
// Check if it possible
// to obtain X or not
foreach(KeyValuePair<int, int> keys in primeX)
{
if (X % keys.Key != 0)
{
return -1;
}
ans += primeX[keys.Key];
}
// Check if it possible to
// obtain Y or not
foreach(KeyValuePair<int, int> keys in primeY)
{
if (Y % keys.Key != 0)
{
return -1;
}
ans += primeY[keys.Key];
}
// Return main ans
return ans;
}
// Driver Code
static void Main()
{
// Given Input
int X = 36;
int Y = 48;
// Function Call
int ans = CountToMakeEqual(X, Y);
Console.Write(ans);
}
}
// This code is contributed by rameshtravel07
Javascript
<script>
// Javascript program for the above approach
function gcd(a, b){
// Everything divides 0
if(b == 0){
return a;
}
return gcd(b, a % b);
}
// Function to calculate total number of
// prime factor with their prime factor
function PrimeFactor(N)
{
let primef = new Map();
// Iterate while the number is even
while (N % 2 == 0)
{
if (primef.has(2))
{
primef.set(2, primef.get(2) + 1);
}
else
{
primef.set(2, 1);
}
// Reduce to half
N = parseInt(N / 2, 10);
}
// Iterate up to sqrt(N)
for(let i = 3; i <= Math.sqrt(N); i++)
{
// Iterate while N has
// factors of i
while (N % i == 0)
{
if (primef.has(i))
{
primef.set(i, primef.get(i) + 1);
}
else
{
primef.set(i, 1);
}
// Removing one factor of i
N = parseInt(N / 2, 10);
}
}
if (N > 2)
{
primef[N] = 1;
}
return primef;
}
// Function to count the number of factors
function CountToMakeEqual(X, Y)
{
// Find the GCD
let gcdofXY = gcd(X, Y);
// Find multiples left in X and Y
let newX = parseInt(Y / gcdofXY, 10);
let newY = parseInt(X / gcdofXY, 10);
// Find prime factor of multiple
// left in X and Y
let primeX = PrimeFactor(newX);
let primeY = PrimeFactor(newY);
// Initialize ans
let ans = 0;
// Check if it possible
// to obtain X or not
primeX.forEach((values,keys)=>
{
if (X % keys != 0)
{
return -1;
}
ans += primeX.get(keys);
})
ans+=1;
// Check if it possible to
// obtain Y or not
primeY.forEach((values,keys)=>
{
if (Y % keys != 0)
{
return -1;
}
ans += primeY.get(keys);
})
// return main ans
return ans;
}
// Given Input
let X = 36;
let Y = 48;
// Function Call
let ans = CountToMakeEqual(X, Y);
document.write(ans);
// This code is contributed by decode2207.
</script>
Producción:
3
Complejidad de tiempo: O(sqrt(max(X, Y)))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por harshitkap00r y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA