文章

2

粉丝

513

获赞

6

访问

16.0k

头像
p1814 约数求和
P1814 复旦大学2018年机试
发布于2021年2月23日 15:11
阅读数 8.3k

这道题用枚举法,即从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;

}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发