C ++中N以下两个数字的倍数之和

在此问题中，我们给出了三个整数M1，M2和N。我们的任务是创建一个程序，以查找N以下两个数字的倍数之和。

在这里，我们将添加N以下所有元素，它们是M1或M2的倍数

让我们举个例子来了解这个问题，

输入值 

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-如果（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的倍数）

x至n个项的倍数之和由下式给出：

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