C++のNより下の2つの数値の倍数の合計

この問題では、3つの整数M1、M2、およびNを指定しました。私たちのタスクは、Nの下の2つの数値の倍数の合計を見つけるプログラムを作成することです。

ここでは、M1またはM2の倍数であるNの下のすべての要素を追加します

問題を理解するために例を見てみましょう

入力

N = 13, M1 = 4, M2 = 6

出力

20

説明 − 13未満の4と6の倍数である数は、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