Tổng tối đa của các số khác biệt với LCM là N trong C ++

Trong bài toán này, chúng ta được cho một số N. Nhiệm vụ của chúng ta là tạo một chương trình để tìm tổng lớn nhất của các số phân biệt với LCM là N trong C ++.

Mô tả vấn đề

Ở đây, chúng ta cần tìm tổng các số lớn nhất có N là Bội số chung thấp nhất (LCM).

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào

N = 10

Đầu ra

18

Giải thích

Maximum sum with LCM 10 is 1 + 2 + 5 + 10 = 18

Phương pháp tiếp cận giải pháp

Một giải pháp đơn giản cho vấn đề là sử dụng ý tưởng rằng nếu chúng ta muốn số N là LCM, thì chúng ta cần lấy tất cả các ước riêng biệt của N. Và cộng chúng lại để có được maxSum.

Đối với điều này, chúng tôi sẽ tìm tất cả các thừa số của N. Và sau đó cộng chúng lại, điều này sẽ được giá trị lớn nhất vì chúng tôi đã xem xét tất cả các số có thể góp phần vào LCM là N.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

#include <iostream>
using namespace std;

int calcFactorSum(int N){
   int maxSum = 0;
   for (int i = 1; i*i <= N; i++){
      if (N % i == 0) {
         if (i == (N/i))
            maxSum = maxSum + i;
         else
            maxSum = maxSum + i + (N/i);
      }
   }
   return maxSum;
}
int main(){
   int N = 42;
   cout<<"The sum of distinct numbers with LCM as "<<N<<" is "<<calcFactorSum(N);
   return 0;
}

Đầu ra

The sum of distinct numbers with LCM as 42 is 96