Compruebe si el MCD de [L, R] se puede hacer > 1 reemplazando pares con su producto como máximo K veces

Dado un rango [L, R] y un entero K , la tarea es verificar si es posible hacer que el GCD de todos los enteros en el rango dado sea mayor que 1 usando como máximo K operaciones en las que cada operación reemplaza dos enteros en el gama con su producto.

Ejemplos:

Entrada: L = 1, R = 5, K = 3 .
Salida: Sí
Explicación: Todos los enteros en el rango dado son {1, 2, 3, 4, 5}. En primera operación sustituir los dos primeros elementos por su producto. Por lo tanto, los elementos restantes se convierten en {2, 3, 4, 5}. Del mismo modo, {2, 3, 4, 5} => {2, 3, 20} => {2, 60}. Por lo tanto, en tres operaciones el rango dado se puede reducir a {2, 60} tal que su MCD sea mayor que 1.

Entrada: L = 1, R = 2, K = 0
Salida: No

Enfoque: el problema dado se puede resolver utilizando un enfoque codicioso . La idea es encontrar el factor primo más común entre todos los enteros del rango para que otros elementos puedan fusionarse con ellos. Se puede observar que el factor primo más común en todos los casos será 2 . Por lo tanto, la opción más óptima es multiplicar todos los enteros impares por su entero par más cercano. Por lo tanto, si el recuento de enteros impares es mayor que K , es posible que no lo sea.

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

// C++ program of the above approach
#include <iostream>
using namespace std;
 
// Function to check if it is possible
// to make GCD of all integers in the
// given range more than 1 with the
// help of at most K operations
bool gcdGreaterThanOne(int L, int R, int K)
{
    // Case where the range
    // has only one integer
    if (L == R) {
        if (L == 1)
            return false;
        else
            return true;
    }
 
    // Stores the count of
    // odd integers in [L, R]
    int odd = (R - L + 1)
              - (R / 2 - ((L - 1) / 2));
 
    return (odd > K) ? false : true;
}
 
// Driver function
int main()
{
    int L = 1;
    int R = 5;
    int K = 3;
 
    if (gcdGreaterThanOne(L, R, K))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG {
 
  // Function to check if it is possible
  // to make GCD of all integers in the
  // given range more than 1 with the
  // help of at most K operations
  static Boolean gcdGreaterThanOne(int L, int R, int K)
  {
    // Case where the range
    // has only one integer
    if (L == R) {
      if (L == 1)
        return false;
      else
        return true;
    }
 
    // Stores the count of
    // odd integers in [L, R]
    int odd = (R - L + 1)
      - (R / 2 - ((L - 1) / 2));
 
    return (odd > K) ? false : true;
  }
 
  // Driver function
  public static void main (String[] args) {
    int L = 1;
    int R = 5;
    int K = 3;
 
    if (gcdGreaterThanOne(L, R, K))
      System.out.println("Yes");  
    else
      System.out.println("No");       
  }
}
 
// This code is contributed by hrithikgarg03188.

# Function to check if it is possible
# to make GCD of all integers in the
# given range more than 1 with the
# help of at most K operations
 
 
def gcdGreaterThanOne(L, R, K):
 
    # Case where the range
    # has only one integer
    if (L == R):
        if (L == 1):
            return false
        else:
            return true
 
    # Stores the count of
    # odd integers in [L, R]
    odd = (R - L + 1) - (R / 2 - ((L - 1) / 2))
 
    return (odd <= K)
 
 
# Driver function
L = 1
R = 5
K = 3
 
if (gcdGreaterThanOne(L, R, K)):
    print("Yes")
else:
    print("No")
 
# This code is contributed by khatriharsh281

// C# implementation for the above approach
using System;
 
class GFG{
 
  // Function to check if it is possible
  // to make GCD of all integers in the
  // given range more than 1 with the
  // help of at most K operations
  static Boolean gcdGreaterThanOne(int L, int R, int K)
  {
     
    // Case where the range
    // has only one integer
    if (L == R) {
      if (L == 1)
        return false;
      else
        return true;
    }
 
    // Stores the count of
    // odd integers in [L, R]
    int odd = (R - L + 1)
      - (R / 2 - ((L - 1) / 2));
 
    return (odd > K) ? false : true;
  }
 
// Driver code
static public void Main (){
 
    int L = 1;
    int R = 5;
    int K = 3;
 
    if (gcdGreaterThanOne(L, R, K))
      Console.Write("Yes");  
    else
      Console.Write("No");
}
}
 
// This code is contributed by sanjoy_62.

<script>
       // JavaScript code for the above approach
 
       // Function to check if it is possible
       // to make GCD of all integers in the
       // given range more than 1 with the
       // help of at most K operations
       function gcdGreaterThanOne(L, R, K)
       {
        
           // Case where the range
           // has only one integer
           if (L == R) {
               if (L == 1)
                   return false;
               else
                   return true;
           }
 
           // Stores the count of
           // odd integers in [L, R]
           let odd = (R - L + 1)
               - (R / 2 - ((L - 1) / 2));
 
           return (odd > K) ? false : true;
       }
 
       // Driver function
       let L = 1;
       let R = 5;
       let K = 3;
 
       if (gcdGreaterThanOne(L, R, K))
           document.write("Yes");
       else
           document.write("No");
 
      // This code is contributed by Potta Lokesh
   </script>

Yes

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)