做图素材网站哪个好,网站建设实践报告小结,聚名网域名备案,网站优化推广给你两个正整数 n 和 m 。
现定义两个整数 num1 和 num2 #xff0c;如下所示#xff1a;
num1#xff1a;范围 [1, n] 内所有 无法被 m 整除 的整数之和。 num2#xff1a;范围 [1, n] 内所有 能够被 m 整除 的整数之和。 返回整数 num1 - num2 。
示例 1#xff1a; …给你两个正整数 n 和 m 。
现定义两个整数 num1 和 num2 如下所示
num1范围 [1, n] 内所有 无法被 m 整除 的整数之和。 num2范围 [1, n] 内所有 能够被 m 整除 的整数之和。 返回整数 num1 - num2 。
示例 1
输入n 10, m 3 输出19 解释在这个示例中
范围 [1, 10] 内无法被 3 整除的整数为 [1,2,4,5,7,8,10] num1 这些整数之和 37 。范围 [1, 10] 内能够被 3 整除的整数为 [3,6,9] num2 这些整数之和 18 。 返回 37 - 18 19 作为答案。 示例 2
输入n 5, m 6 输出15 解释在这个示例中
范围 [1, 5] 内无法被 6 整除的整数为 [1,2,3,4,5] num1 这些整数之和 15 。范围 [1, 5] 内能够被 6 整除的整数为 [] num2 这些整数之和 0 。 返回 15 - 0 15 作为答案。 示例 3
输入n 5, m 1 输出-15 解释在这个示例中
范围 [1, 5] 内无法被 1 整除的整数为 [] num1 这些整数之和 0 。范围 [1, 5] 内能够被 1 整除的整数为 [1,2,3,4,5] num2 这些整数之和 15 。 返回 0 - 15 -15 作为答案。
提示
1 n, m 1000
法一先用求和公式计算出1到n的和nsum再算出n/m的结果k然后用求和公式算出1到k的和乘m即num2num1等于nsum-num2
class Solution {
public:int differenceOfSums(int n, int m) {int nsum (1 n) * n / 2;int division n / m;int num2 ((1 division) * division / 2) * m;int num1 nsum - num2;return num1 - num2;}
};此算法时间复杂度为O(1)空间复杂度为O(1)。
法二直接模拟
class Solution {
public:int differenceOfSums(int n, int m) {int num1 0;int num2 0;for (int i 1; i n; i){if (i % m){num1 i;}else{num2 i;}}return num1 - num2;}
};此算法时间复杂度为O(n)空间复杂度为O(1)。
