数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中求两个数的倍数之和（小于 N）
在这个问题中，我们给定三个整数 M1、M2 和 N。我们的任务是创建一个程序来找到两个数的倍数之和（小于 N）。
在这里，我们将添加所有小于 N 且是 M1 或 M2 的倍数的元素。
让我们举个例子来理解这个问题，
输入
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)，则 sum += i
步骤 2 - 返回 sum。
示例
程序说明了解决方案的工作原理，
#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
更新于: 2020-08-06
289 次浏览
广告