文章

0

粉丝

0

获赞

1

访问

435

头像
p1814 约数求和
P1814
发布于2021年2月23日 15:11
阅读数 101

这道题用枚举法,即从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;
    ...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发