Dado un entero positivo N , la tarea es dividirlo en K partes únicas de manera que la suma de estas partes sea igual al número original y el mcd de todas las partes sea máximo. Imprime el gcd máximo si existe tal división; de lo contrario, imprime -1 .
Ejemplos:
Entrada: N = 6, K = 3
Salida: 1 Las
únicas divisiones posibles con
elementos únicos son (1, 2, 3) y mcd(1, 2, 3) = 1.
Entrada: N = 18, K = 3
Salida: 3
Enfoque ingenuo: encuentre todas las divisiones posibles de N y calcule el gcd máximo de ellas. Pero este enfoque tomará un tiempo y un espacio exponenciales.
Enfoque eficiente: Sean las divisiones de N A 1 , A 2 ……..A K
Ahora, se sabe que mcd(a, b) = mcd(a, b, a + b) y por lo tanto, mcd(A 1 , A 2 ….A K ) = mcd(A 1 , A 2 ….A K , A 1 + A 2 …. + A K )
Pero A 1 + A 2…. + A K = N y por tanto, el mcd de las divisiones será uno de los factores de N .
Sea a el factor de N que puede ser la posible respuesta:
Como a es el mcd, todas las divisiones serán múltiplos de a y por lo tanto, para K único B i ,
a * B 1 + a * B 2 ……. + a * B K = N
a * (B 1 + B 2 …….+ B K ) = N
Como todos los B i son únicos,
B 1+ B 2 …….+ B K ≥ 1 + 2 + 3 ….. + K
B 1 + B 2 …….+ B K ≥ K * (K + 1) / 2
Por lo tanto, todos los factores de N cuyo complementario factor es mayor o igual a K * (K + 1) / 2 puede ser una de las posibles respuestas, y hemos llevado al máximo de todas las posibles respuestas.
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate maximum GCD
int maxGCD(int N, int K)
{
// Minimum possible sum for
// K unique positive integers
int minSum = (K * (K + 1)) / 2;
// It is not possible to divide
// N into K unique parts
if (N < minSum)
return -1;
// All the factors greater than sqrt(N)
// are complementary of the factors less
// than sqrt(N)
int i = sqrt(N);
int res = 1;
while (i >= 1) {
// If i is a factor of N
if (N % i == 0) {
if (i >= minSum)
res = max(res, N / i);
if (N / i >= minSum)
res = max(res, i);
}
i--;
}
return res;
}
// Driver code
int main()
{
int N = 18, K = 3;
cout << maxGCD(N, K);
return 0;
}
Java
// Java implementation of the approach
import java.io.*;
import java.lang.Math;
class GFG
{
// Function to calculate maximum GCD
static int maxGCD(int N, int K)
{
// Minimum possible sum for
// K unique positive integers
int minSum = (K * (K + 1)) / 2;
// It is not possible to divide
// N into K unique parts
if (N < minSum)
return -1;
// All the factors greater than sqrt(N)
// are complementary of the factors less
// than sqrt(N)
int i = (int) Math.sqrt(N);
int res = 1;
while (i >= 1)
{
// If i is a factor of N
if (N % i == 0)
{
if (i >= minSum)
res = Math.max(res, N / i);
if (N / i >= minSum)
res = Math.max(res, i);
}
i--;
}
return res;
}
// Driver code
public static void main (String[] args)
{
int N = 18, K = 3;
System.out.println(maxGCD(N, K));
}
}
// This code is contributed by ApurvaRaj
Python
# Python3 implementation of the approach from math import sqrt,ceil,floor # Function to calculate maximum GCD def maxGCD(N, K): # Minimum possible sum for # K unique positive integers minSum = (K * (K + 1)) / 2 # It is not possible to divide # N into K unique parts if (N < minSum): return -1 # All the factors greater than sqrt(N) # are complementary of the factors less # than sqrt(N) i = ceil(sqrt(N)) res = 1 while (i >= 1): # If i is a factor of N if (N % i == 0): if (i >= minSum): res = max(res, N / i) if (N / i >= minSum): res = max(res, i) i-=1 return res # Driver code N = 18 K = 3 print(maxGCD(N, K)) # This code is contributed by mohit kumar 29
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to calculate maximum GCD
static int maxGCD(int N, int K)
{
// Minimum possible sum for
// K unique positive integers
int minSum = (K * (K + 1)) / 2;
// It is not possible to divide
// N into K unique parts
if (N < minSum)
return -1;
// All the factors greater than sqrt(N)
// are complementary of the factors less
// than sqrt(N)
int i = (int) Math.Sqrt(N);
int res = 1;
while (i >= 1)
{
// If i is a factor of N
if (N % i == 0)
{
if (i >= minSum)
res = Math.Max(res, N / i);
if (N / i >= minSum)
res = Math.Max(res, i);
}
i--;
}
return res;
}
// Driver code
public static void Main()
{
int N = 18, K = 3;
Console.WriteLine(maxGCD(N, K));
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// javascript implementation of the approach
// Function to calculate maximum GCD
function maxGCD(N , K) {
// Minimum possible sum for
// K unique positive integers
var minSum = (K * (K + 1)) / 2;
// It is not possible to divide
// N into K unique parts
if (N < minSum)
return -1;
// All the factors greater than sqrt(N)
// are complementary of the factors less
// than sqrt(N)
var i = parseInt( Math.sqrt(N));
var res = 1;
while (i >= 1) {
// If i is a factor of N
if (N % i == 0) {
if (i >= minSum)
res = Math.max(res, N / i);
if (N / i >= minSum)
res = Math.max(res, i);
}
i--;
}
return res;
}
// Driver code
var N = 18, K = 3;
document.write(maxGCD(N, K));
// This code contributed by Rajput-Ji
</script>
3
Complejidad de tiempo: O(N 1/2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por AshaRamMeena y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA