LCM为N的不同数的最大和-yiteyi-C++库

给定一个数N，任务是找出不同数的最大和，使所有这些数的最小公倍数为N。

null

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

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

我们可以通过观察一些情况来解决这个问题，因为N需要是所有数的LCM，所有这些数都将是N的除数，但是因为一个数只能求和一次，所以所有求和的数都应该是不同的。我们的想法是 N的每个除数求和一次 使结果最大化。我们怎么能说我们得到的和是最大和呢？原因是，我们已经把N的所有除数都带进了求和，现在如果我们再把一个不是N的除数的数带进求和，那么求和会增加，但LCM属性不会被所有这些整数保持。所以，除了N的所有除数，我们不可能在求和中再加一个数，所以我们的问题归结为，给定N，求所有除数的和，这可以在O（sqrt（N））时间内解决。所以解的总时间复杂度为O（sqrt（N））和O（1）额外空间。下面给出了上述概念的代码。请参考这寻找一个数的所有除数的帖子。

C++

                         // 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

                         // 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.                       

Python3

                         # 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#

                         // 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                       
                         //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                                     ),                                     ""                                     ;                       
           
                         // This code is contributed by ajit                       
                         ?>                       

Javascript

                         <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>                       

输出：

本文由 乌特卡什·特里维迪 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用贡献极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章