文章
0
粉丝
0
获赞
1
访问
435
这道题用枚举法,即从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;
...
登录后发布评论
暂无评论,来抢沙发