Рубрики

Максимальная сумма различных чисел с LCM как N

Для заданного числа N задача состоит в том, чтобы найти максимальную сумму различных чисел, чтобы наименьшее общее кратное всех этих чисел было равно 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 

Мы можем решить эту проблему, наблюдая некоторые случаи: поскольку N должен быть LCM всех чисел, все они будут делителями N, но поскольку число может быть взято только один раз в сумме, все взятые числа должны быть различны. Идея состоит в том, чтобы взять каждый делитель N один раз в сумме, чтобы максимизировать результат.
Как мы можем сказать, что полученная нами сумма является максимальной? Причина в том, что мы взяли все делители N в нашу сумму, теперь, если мы возьмем в сумму еще одно число, не являющееся делителем N, тогда сумма будет увеличиваться, но свойство LCM не будет поддерживаться всеми этими целыми числами. Таким образом, невозможно добавить еще одну цифру в нашу сумму, кроме всех делителей N, поэтому наша проблема сводится к этому, учитывая, что N найти сумму всех делителей, которая может быть решена за время O (sqrt (N)).
Таким образом, общая временная сложность решения будет O (sqrt (N)) с O (1) дополнительным пространством.

Код приведен ниже по вышеуказанной концепции. Пожалуйста, обратитесь к этому сообщению, чтобы найти все делители числа.

C ++

// C / C ++ программа для получения максимальной суммы чисел
// с условием, что их LCM должен быть N
#include <bits/stdc++.h>

using namespace std;

  
// Метод возвращает максимальную сумму
// номер, чей LCM равен N

int getMaximumSumWithLCMN(int N)

{

    int sum = 0;

    int LIM = sqrt(N);

  

    // найти все делители, которые делят 'N'

    for (int i = 1; i <= LIM; i++) {

        // если 'i' является делителем 'N'

        if (N % i == 0) {

            // если оба делителя одинаковы, добавить

            // это только один раз добавить оба

            if (i == (N / i))

                sum += i;

            else

                sum += (i + N / i);

        }

    }

  

    return sum;

}

  
// Код драйвера для тестирования вышеуказанных методов

int main()

{

    int N = 12;

    cout << getMaximumSumWithLCMN(N) << endl;

    return 0;

}

Джава

// Java-программа для получения
// максимальная сумма чисел
// с условием, что
// их LCM должен быть N

  

class GFG {

    // Метод возвращает максимум

    // сумма f отличное число

    // чей LCM равен N

    static int getMaximumSumWithLCMN(int N)

    {

        int sum = 0;

        int LIM = (int)Math.sqrt(N);

  

        // найти все делители, которые делят 'N'

        for (int i = 1; i <= LIM; i++) {

            // если 'i' является делителем 'N'

            if (N % i == 0) {

                // если оба делителя одинаковы, добавить

                // это только один раз добавить оба

                if (i == (N / i))

                    sum += i;

                else

                    sum += (i + N / i);

            }

        }

  

        return sum;

    }

  

    // Код драйвера

    public static void main(String[] args)

    {

        int N = 12;

        System.out.println(getMaximumSumWithLCMN(N));

    }

}

  
// Этот код предоставлен Anant Agarwal.

python3

# Python программа для получения
# максимальная сумма чисел
# с условием, что
# их LCM должен быть N

  

import math

  
# Метод возвращает максимальную сумму
# номер, чей LCM равен N

def getMaximumSumWithLCMN(N):

  

    sum = 0

    LIM = int(math.sqrt(N))

   

    # найти все делители, которые делят 'N'

    for i in range(1, LIM + 1):

  

        # если 'i' является делителем 'N'

        if (N % i == 0):

  

            # если оба делителя одинаковы, добавьте

            # это только один раз добавить оба

            if (i == (N // i)):

                sum = sum + i

            else:

                sum = sum + (i + N // i)

       

    return sum

  
# код водителя

  

N = 12

print(getMaximumSumWithLCMN(N))

  
# Этот код добавлен
# Анант Агарвал.

C #

// C # программа для получения максимальной суммы
// чисел с условием, что
// их LCM должен быть N

using System;

  

class GFG {

      

    // Метод возвращает максимальную сумму f

    // отдельный номер, чей LCM равен N

    static int getMaximumSumWithLCMN(int N)

    {

        int sum = 0;

        int LIM = (int)Math.Sqrt(N);

  

        // Найти все делители, которые делят 'N'

        for (int i = 1; i <= LIM; i++) {

              

            // если 'i' является делителем 'N'

            if (N % i == 0) {

                  

                // если оба делителя одинаковы

                // добавить его только один раз, добавить оба

                if (i == (N / i))

                    sum += i;

                else

                    sum += (i + N / i);

            }

        }

  

        return sum;

    }

  

    // Код драйвера

    public static void Main()

    {

        int N = 12;

        Console.Write(getMaximumSumWithLCMN(N));

    }

}

  
// Этот код предоставлен нитин митталь

PHP

<?php
// программа php, чтобы найти максимальную сумму
// числа с lcm равным n

  
// Возвращает максимальную сумму чисел с
// LCM как N

function maxSumLCM($n)

{

    $max_sum = 0; // Инициализировать результат

  

    // Находим делитель n и добавляем

    // это до 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;

}

  
// Код драйвера

$n = 2;

echo MaxSumLCM($n), "\n";

  
// Этот код предоставлен ajit
?>


Выход:

28

Эта статья предоставлена Уткаршем Триведи . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Максимальная сумма различных чисел с LCM как N

0.00 (0%) 0 votes