Dados los números enteros positivos, X , Y y N , la tarea es verificar si X puede hacerse igual a Y en exactamente N operaciones en las que cada operación:
- X se puede dividir por cualquiera de sus factores que no sea 1.
- Y se puede dividir por cualquiera de sus factores que no sea 1.
Ejemplos:
Entrada: X = 4, Y = 21, N = 3
Salida: Sí
Explicación: Tanto X como Y pueden igualarse realizando las siguientes operaciones:
X = X/4, Y = Y/3, Y = Y/7, que da como resultado tanto X como Y como 1.
También hay varias otras formas de hacer que ambos sean iguales en tres operaciones.
Como X = X/2, X = X/2, Y = Y/21.Entrada: X = 5, Y = 17, N = 3
Salida: No
Planteamiento: La idea para resolver el problema se basa en la siguiente observación:
- El problema se puede resolver haciendo que ambos números sean 1.
- El número mínimo de veces para dividir un número para obtener 1 es dividir el número por sí mismo. Y el número máximo de veces para obtener 1 es la suma de los exponentes de todos los factores primos.
- Cualquier número natural N se puede escribir en términos del producto de sus factores primos como:
N = p 1 n1 .p 2 n2 . . . p k nk , donde p 1, p 2 . . . p k son números primos distintos.- Entonces, el número máximo de veces que se puede dividir N es igual a n1 + n2 + …. + nk .
- Si el máximo divisor de X e Y combinados es mayor o igual a N , ambos pueden hacerse iguales, de lo contrario no.
Siga los pasos mencionados a continuación para implementar la observación anterior:
- Si N es igual a 1:
- Si uno entre X e Y es el factor del otro, entonces pueden hacerse iguales.
- De lo contrario, no se pueden hacer iguales.
- De lo contrario, si N es menor o igual que el número máximo de factores de X e Y, entonces se pueden igualar.
- De lo contrario, no hay solución posible.
A continuación se muestra la implementación del enfoque anterior de manera optimizada:
C++
// C++ code to implement above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find total
// number of times we can
// divide a number before making it 1.
int count(int val)
{
int ans = 0;
// Checking how many times
// the number can be
// divided by 2.
while (val % 2 == 0) {
ans++;
val = val / 2;
}
// Iterating through each number from
// 3 to sqrt(val) and finding how many
// times the number can be divide
for (int i = 3; i <= sqrt(val); i = i + 2) {
while (val % i == 0) {
ans++;
val = val / i;
}
}
if (val > 2)
ans++;
return ans;
}
// Function to return if
// we can make x and y equal or not
int solve(int x, int y, int n)
{
if (n == 0) {
if (x == y) {
cout << "Yes";
}
else {
cout << "No";
}
}
else if (n == 1) {
if ((x % y == 0 || y % x == 0)
&& x != y) {
cout << "Yes";
}
else {
cout << "No";
}
}
else {
if (count(x) + count(y) >= n) {
cout << "Yes";
}
else {
cout << "No";
}
}
}
// Driver code
int main()
{
int X = 4, Y = 21, N = 3;
// Function call
solve(X, Y, N);
return 0;
}
Java
// Java code to implement above approach
import java.io.*;
class GFG
{
// Function to find total
// number of times we can
// divide a number before making it 1.
static int count(int val)
{
int ans = 0;
// Checking how many times
// the number can be
// divided by 2.
while (val % 2 == 0) {
ans++;
val = val / 2;
}
// Iterating through each number from
// 3 to sqrt(val) and finding how many
// times the number can be divide
for (int i = 3; i <= Math.sqrt(val); i = i + 2) {
while (val % i == 0) {
ans++;
val = val / i;
}
}
if (val > 2)
ans++;
return ans;
}
// Function to return if
// we can make x and y equal or not
static void solve(int x, int y, int n)
{
if (n == 0) {
if (x == y) {
System.out.print("Yes");
}
else {
System.out.print("No");
}
}
else if (n == 1) {
if ((x % y == 0 || y % x == 0)
&& x != y) {
System.out.print("Yes");
}
else {
System.out.print("No");
}
}
else {
if (count(x) + count(y) >= n) {
System.out.print("Yes");
}
else {
System.out.print("No");
}
}
}
// Driver code
public static void main (String[] args) {
int X = 4, Y = 21, N = 3;
// Function call
solve(X, Y, N);
}
}
// This code is contributed by hrithikgarg03188.
Python3
# Python3 code to implement above approach
# Function to find total
# number of times we can
# divide a number before making it 1.
def count(val):
ans = 0
# Checking how many times
# the number can be
# divided by 2.
while (val % 2 == 0):
ans += 1
val = val // 2
# Iterating through each number from
# 3 to sqrt(val) and finding how many
# times the number can be divide
for i in range(3, int(val**0.5)+1, 2):
while (val % i == 0):
ans += 1
val = val // i
if (val > 2):
ans += 1
return ans
# Function to return if
# we can make x and y equal or not
def solve(x, y, n):
if (n == 0):
if (x == y):
print("Yes")
else:
print("No")
elif (n == 1):
if ((x % y == 0 or y % x == 0) and x != y):
print("Yes")
else:
print("No")
else:
if (count(x) + count(y) >= n):
print("Yes")
else:
print("No")
# Driver code
if __name__ == "__main__":
x = 4
y = 21
n = 3
solve(x, y, n)
# This code is contributed by amnindersingh1414.
C#
// C# code to implement above approach
using System;
public class GFG {
// Function to find total
// number of times we can
// divide a number before making it 1.
static int count(int val)
{
int ans = 0;
// Checking how many times
// the number can be
// divided by 2.
while (val % 2 == 0) {
ans++;
val = val / 2;
}
// Iterating through each number from
// 3 to sqrt(val) and finding how many
// times the number can be divide
for (int i = 3; i <= Math.Sqrt(val); i = i + 2) {
while (val % i == 0) {
ans++;
val = val / i;
}
}
if (val > 2)
ans++;
return ans;
}
// Function to return if
// we can make x and y equal or not
static void solve(int x, int y, int n)
{
if (n == 0) {
if (x == y) {
Console.Write("Yes");
}
else {
Console.Write("No");
}
}
else if (n == 1) {
if ((x % y == 0 || y % x == 0) && x != y) {
Console.Write("Yes");
}
else {
Console.Write("No");
}
}
else {
if (count(x) + count(y) >= n) {
Console.Write("Yes");
}
else {
Console.Write("No");
}
}
}
// Driver code
public static int Main()
{
int X = 4, Y = 21, N = 3;
// Function call
solve(X, Y, N);
return 0;
}
}
// This code is contributed by Taranpreet
Javascript
<script>
// JavaScript code to implement above approach
// Function to find total
// number of times we can
// divide a number before making it 1.
const count = (val) => {
let ans = 0;
// Checking how many times
// the number can be
// divided by 2.
while (val % 2 == 0) {
ans++;
val = parseInt(val / 2);
}
// Iterating through each number from
// 3 to sqrt(val) and finding how many
// times the number can be divide
for (let i = 3; i <= parseInt(Math.sqrt(val)); i = i + 2) {
while (val % i == 0) {
ans++;
val = parseInt(val / i);
}
}
if (val > 2)
ans++;
return ans;
}
// Function to return if
// we can make x and y equal or not
const solve = (x, y, n) => {
if (n == 0) {
if (x == y) {
document.write("Yes");
}
else {
document.write("No");
}
}
else if (n == 1) {
if ((x % y == 0 || y % x == 0)
&& x != y) {
document.write("Yes");
}
else {
document.write("No");
}
}
else {
if (count(x) + count(y) >= n) {
document.write("Yes");
}
else {
document.write("No");
}
}
}
// Driver code
let X = 4, Y = 21, N = 3;
// Function call
solve(X, Y, N);
// This code is contributed by rakeshsahni
</script>
Producción
Yes
Complejidad temporal: O(√X)+ √Y)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por pushpeshrajdx01 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA