El entero positivo más pequeño X que satisface la ecuación dada

Dados dos enteros N y K , la tarea es encontrar el entero positivo más pequeño X que satisfaga la ecuación:

(X/K) * (X % K) = N

Ejemplos:  

Entrada: N = 6, K = 3 
Salida: 11 
Explicación: 
Para X = 11, (11 / 3) * (11 % 3) = 3 * 2 = 6 
Por lo tanto, la siguiente ecuación satisface.

Entrada: N = 4, K = 6 
Salida: 10 
Explicación: 
Para X = 10, (10 / 6) * (10 % 6) = 1 * 4 = 4 
Por lo tanto, la siguiente ecuación satisface. 
 

Acercarse: 

La idea es observar que, dado que (X / K) * (X % K) = N , por lo tanto, N será divisible por p = X % K , que es menor que K . Por lo tanto, para todo i en el rango [1, K) pruebe todos los valores de p donde: 

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

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find out the smallest
// positive integer for the equation
int findMinSoln(int n, int k)
{
    // Stores the minimum
    int minSoln = INT_MAX;
 
    // Iterate till K
    for (int i = 1; i < k; i++) {
 
        // Check if n is divisible by i
        if (n % i == 0)
            minSoln
                = min(minSoln, (n / i) * k + i);
    }
 
    // Return the answer
    return minSoln;
}
 
// Driver Code
int main()
{
    int n = 4, k = 6;
    cout << findMinSoln(n, k);
}

// Java Program to implement
// the above approach
import java.util.*;
class GFG{
  
// Function to find out the smallest
// positive integer for the equation
static int findMinSoln(int n, int k)
{
    // Stores the minimum
    int minSoln = Integer.MAX_VALUE;
  
    // Iterate till K
    for (int i = 1; i < k; i++)
    {
  
        // Check if n is divisible by i
        if (n % i == 0)
            minSoln = Math.min(minSoln, (n / i) * k + i);
    }
  
    // Return the answer
    return minSoln;
}
  
// Driver Code
public static void main(String[] args)
{
    int n = 4, k = 6;
    System.out.println(findMinSoln(n, k));
}
}
 
// This code is contributed by Ritik Bansal

# Python3 program to implement
# the above approach
import sys
 
# Function to find out the smallest
# positive integer for the equation
def findMinSoln(n, k):
     
    # Stores the minimum
    minSoln = sys.maxsize;
 
    # Iterate till K
    for i in range(1, k):
 
        # Check if n is divisible by i
        if (n % i == 0):
            minSoln = min(minSoln, (n // i) * k + i);
     
    # Return the answer
    return minSoln;
 
# Driver Code
if __name__ == '__main__':
     
    n = 4;
    k = 6;
     
    print(findMinSoln(n, k));
 
# This code is contributed by amal kumar choubey

// C# program to implement
// the above approach
using System;
 
class GFG{
 
// Function to find out the smallest
// positive integer for the equation
static int findMinSoln(int n, int k)
{
     
    // Stores the minimum
    int minSoln = int.MaxValue;
 
    // Iterate till K
    for (int i = 1; i < k; i++)
    {
 
        // Check if n is divisible by i
        if (n % i == 0)
            minSoln = Math.Min(minSoln,
                              (n / i) * k + i);
    }
 
    // Return the answer
    return minSoln;
}
 
// Driver Code
public static void Main(String[] args)
{
    int n = 4, k = 6;
     
    Console.WriteLine(findMinSoln(n, k));
}
}
 
// This code is contributed by amal kumar choubey

<script>
 
 
// Javascript Program to implement
// the above approach
 
// Function to find out the smallest
// positive integer for the equation
function findMinSoln(n, k)
{
 
    // Stores the minimum
    var minSoln = 1000000000;
 
    // Iterate till K
    for (var i = 1; i < k; i++) {
 
        // Check if n is divisible by i
        if (n % i == 0)
            minSoln
                = Math.min(minSoln, (n / i) * k + i);
    }
 
    // Return the answer
    return minSoln;
}
 
// Driver Code
var n = 4, k = 6;
document.write( findMinSoln(n, k));
 
// This code is contributed by rutvik_56.
</script>

10

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