C++에서 LCM이 N인 고유 숫자의 최대 합계

이 문제에서는 숫자 N이 주어집니다. 우리의 임무는 C++에서 LCM을 N으로 사용하여 고유한 숫자의 최대 합을 찾는 프로그램을 만드는 것입니다.

문제 설명

여기서 N이 LCM(최저공배수)인 최대 수의 합을 찾아야 합니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력

N = 10

출력

18

설명

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

솔루션 접근 방식

문제에 대한 간단한 솔루션은 숫자 N을 LCM으로 원할 경우 N의 고유한 제수를 모두 가져와야 한다는 아이디어를 사용하는 것입니다. 그리고 그것들을 더하여 maxSum을 구해야 합니다.

이를 위해 우리는 N의 모든 요소를 ​​찾을 것입니다. 그런 다음 이들을 더하면 LCM에 기여할 수 있는 모든 숫자가 N인 것을 고려하므로 최대값이 주어집니다.

예시

솔루션의 작동을 설명하는 프로그램,

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

출력

The sum of distinct numbers with LCM as 42 is 96