Suma máxima de números distintos con LCM como N

Dado un número N, la tarea es encontrar la suma máxima de números distintos tal que el Mínimo Común Múltiplo de todos estos números sea N.
 

Input  : N = 12
Output : 20
Maximum sum which we can achieve is,
1 + 2 + 3 + 4 + 6 + 12 = 28

Input  : N = 15
Output : 24 

Podemos resolver este problema observando algunos casos, como N debe ser mcm de todos los números, todos ellos serán divisores de N, pero debido a que un número se puede tomar solo una vez en la suma, todos los números tomados deben ser distintos. La idea es tomar todos los divisores de N una vez en la suma para maximizar el resultado. 
¿Cómo podemos decir que la suma que obtuvimos es la suma máxima? La razón es que hemos tomado todos los divisores de N en nuestra suma, ahora si tomamos un número más en la suma que no es divisor de N, entonces la suma aumentará pero la propiedad MCM no se mantendrá en todos esos números enteros. Por lo tanto, no es posible agregar ni un número más a nuestra suma, excepto todos los divisores de N, por lo que nuestro problema se reduce a esto, dado que N encuentra la suma de todos los divisores, que se puede resolver en tiempo O (raíz cuadrada (N)). 
Entonces, la complejidad temporal total de la solución será O (sqrt (N)) con O (1) espacio adicional. 
El código se proporciona a continuación sobre el concepto mencionado anteriormente. Consulte esta publicación para encontrar todos los divisores de un número. 
 

// C/C++ program to get maximum sum of Numbers
// with condition that their LCM should be N
#include <bits/stdc++.h>
using namespace std;
 
// Method returns maximum sum f distinct
// number whose LCM is N
int getMaximumSumWithLCMN(int N)
{
    int sum = 0;
    int LIM = sqrt(N);
 
    // find all divisors which divides 'N'
    for (int i = 1; i <= LIM; i++) {
        // if 'i' is divisor of 'N'
        if (N % i == 0) {
            // if both divisors are same then add
            // it only once else add both
            if (i == (N / i))
                sum += i;
            else
                sum += (i + N / i);
        }
    }
 
    return sum;
}
 
// Driver code to test above methods
int main()
{
    int N = 12;
    cout << getMaximumSumWithLCMN(N) << endl;
    return 0;
}

// Java program to get
// maximum sum of Numbers
// with condition that
// their LCM should be N
 
class GFG {
    // Method returns maximum
    // sum f distinct number
    // whose LCM is N
    static int getMaximumSumWithLCMN(int N)
    {
        int sum = 0;
        int LIM = (int)Math.sqrt(N);
 
        // find all divisors which divides 'N'
        for (int i = 1; i <= LIM; i++) {
            // if 'i' is divisor of 'N'
            if (N % i == 0) {
                // if both divisors are same then add
                // it only once else add both
                if (i == (N / i))
                    sum += i;
                else
                    sum += (i + N / i);
            }
        }
 
        return sum;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int N = 12;
        System.out.println(getMaximumSumWithLCMN(N));
    }
}
 
// This code is contributed by Anant Agarwal.

# Python program to get
# maximum sum of Numbers
# with condition that
# their LCM should be N
 
import math
 
# Method returns maximum sum f distinct
# number whose LCM is N
def getMaximumSumWithLCMN(N):
 
    sum = 0
    LIM = int(math.sqrt(N))
  
    # find all divisors which divides 'N'
    for i in range(1, LIM + 1):
 
        # if 'i' is divisor of 'N'
        if (N % i == 0):
 
            # if both divisors are same then add
            # it only once else add both
            if (i == (N // i)):
                sum = sum + i
            else:
                sum = sum + (i + N // i)
      
    return sum
 
# driver code
 
N = 12
print(getMaximumSumWithLCMN(N))
 
# This code is contributed
# by Anant Agarwal.

// C# program to get maximum sum
// of Numbers with condition that
// their LCM should be N
using System;
 
class GFG {
     
    // Method returns maximum sum f
    // distinct number whose LCM is N
    static int getMaximumSumWithLCMN(int N)
    {
        int sum = 0;
        int LIM = (int)Math.Sqrt(N);
 
        // Find all divisors which divides 'N'
        for (int i = 1; i <= LIM; i++) {
             
            // if 'i' is divisor of 'N'
            if (N % i == 0) {
                 
                // if both divisors are same then
                // add it only once else add both
                if (i == (N / i))
                    sum += i;
                else
                    sum += (i + N / i);
            }
        }
 
        return sum;
    }
 
    // Driver code
    public static void Main()
    {
        int N = 12;
        Console.Write(getMaximumSumWithLCMN(N));
    }
}
 
// This code is contributed by nitin mittal

<?php
//php program to find the max sum of
// numbers whose lcm is n
 
// Returns maximum sum of numbers with
// LCM as N
function maxSumLCM($n)
{
    $max_sum = 0; // Initialize result
 
    // Finding a divisor of n and adding
    // it to max_sum
    for ($i = 1; $i * $i <= $n; $i++)
    {
        if ($n % $i == 0)
        {
            $max_sum += $i;
            if ($n/$i != $i)
                $max_sum += ($n / $i);
        }
    }
 
    return $max_sum;
}
 
// Driver code
$n = 2;
echo MaxSumLCM($n), "\n";
 
// This code is contributed by ajit
?>

<script>
 
// Javascript program to get maximum sum of Numbers
// with condition that their LCM should be N
 
// Method returns maximum sum f distinct
// number whose LCM is N
function getMaximumSumWithLCMN(N)
{
    let sum = 0;
    let LIM = Math.sqrt(N);
 
    // find all divisors which divides 'N'
    for (let i = 1; i <= LIM; i++)
    {
     
        // if 'i' is divisor of 'N'
        if (N % i == 0)
        {
         
            // if both divisors are same then add
            // it only once else add both
            if (i == (N / i))
                sum += i;
            else
                sum += (i + N / i);
        }
    }
    return sum;
}
 
// Driver code to test above methods
    let N = 12;
    document.write(getMaximumSumWithLCMN(N) + "<br>");
 
// This code is contributed by Mayank Tyagi
 
</script>

Producción: 
 

28

Complejidad temporal: O(√n) 
Espacio auxiliar: O(1)

Este artículo es una contribución de Aarti_Rathi y Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.