C++에서 N 아래의 두 숫자의 배수의 합

이 문제에서 우리는 세 개의 정수 M1, M2, N을 주었습니다. 우리의 임무는 N 아래의 두 숫자의 배수의 합을 찾는 프로그램을 만드는 것입니다.

여기에서 M1 또는 M2의 배수인 N 아래의 모든 요소를 ​​추가합니다.

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

입력

N = 13, M1 = 4, M2 = 6

출력

20

설명 − 4와 6의 배수 중 13보다 작은 수는 4, 6, 8, 12입니다.

문제에 대한 간단한 해결책은 1에서 N까지 반복하고 M1 또는 M2로 나눌 수 있는 모든 값을 더하는 것입니다.

알고리즘

1단계 − sum =0 , i =0. i =1에서 N까지 루프.

1.1단계 - if (i%M1 ==0) 또는 (i%M2 ==0), 합계 + =i

2단계 - 반환 합계.

예

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

#include <iostream<
using namespace std;
int calcMulSum(int N, int M1, int M2){
   int sum = 0;
   for (int i = 0; i < N; i++)
      if (i%M1 == 0 || i%M2 == 0)
   sum += i;
   return sum;
}
int main(){
   int N = 24, M1 = 4, M2 = 7;
   cout<<"The sum of multiples of "<<M1<<" and "<<M2<<" below "<<N<<" is "<<calcMulSum(N, M1, M2);
   return 0;
}

출력

The sum of multiples of 4 and 7 below 24 is 102

이것은 O(n) 시간 복잡도가 걸리기 때문에 우리 문제에 대한 최선의 솔루션이 아닙니다.

더 나은 솔루션은 급수의 합에 대해 수학 공식을 사용하는 것입니다.

여기서는 급수의 합에 대한 공식을 사용합니다. 최종 합계는 (M1의 배수 + M2의 배수 - M1*M2의 배수)입니다.

n항까지 x의 배수의 합은 다음과 같습니다.

Sum(X) = (n * (1+n) * X)/2

합계를 공식화해 보겠습니다.

sum = ( ( ((n/M1)*(1+(n/M1))*M1)/2) + ((n/M2)*(1+(n/M2))*M2)/2 ) - ((n/M1*M2)*(1+(n/M1*M2))*M1*M2)/2 ) )

예

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

#include <iostream>
using namespace std;
int calcMulSum(int N, int M1, int M2){
   N--;
   return (((N/M1) * (1 + (N/M1)) * M1 / 2) + ((N/M2) * (1 + (N/M2)) * M2 / 2) - ((N/(M1*M2)) * (1 + (N/(M1*M2))) * (M1*M2) / 2));
}
int main(){
   int N = 24, M1 = 4, M2 = 7;
   cout<<"The sum of multiples of "<<M1<<" and "<<M2<<" below "<<N<<" is "<<calcMulSum(N, M1, M2);
   return 0;
}

출력

The sum of multiples of 4 and 7 below 24 is 102