文章
2
粉丝
513
获赞
6
访问
16.0k
这道题用枚举法,即从1到n依次计算各个数的约数之和,由于n过大,则程序运行会超时。
我们可以换一种方式考虑这个问题:
假如现在n=7,即计算1,2,3,4,5,6,7这7个数每个数的约数之和。
每个数的约数分别是:
1:1
2:1 2
3:1 3
4:1 2 4
5:1 5
6:1 2 3 6
7:1 7
我们可以看到约数1出现了7(n)次,约数2出现了3(n/2)次,约数4,5,6,7各出现1次.
也就是说对于一个整数n来说,约数i出现的次数为: n/i,(i=1,2,3...n/2),而对于n/2之后的约数均出现一次。
所以我们可以通过一个for循环来计算n/2及之前的约数出现的次数。利用等差数列求和公式计算之后约数的总和。
代码如下:
#include <iostream>
using namespace std;
int main() {
long long int n, count = 0;
cin >> n;
for (long long int i = 1; i <= n / 2; ++i) {
//计算[1,n/2]各个约数出现的次数(n/i),结果*i就是约数i的总和
count += n / i * i;
}
//计算[n/2+1,n]各个约数出现的次数
//这个范围内的约数只出现一次,因此用等差数列求和公式计算
count += (n - n / 2) * (n / 2 + 1 + n) / 2;
cout << count << endl;
}
登录后发布评论
暂无评论,来抢沙发