乐趣区

AtCoder-Context-ABC-172-D-Sum-of-Divisors

jiezi

本文章为原创文章，未经过允许不得转载
运行要求
运行时间限制: 2sec
内存限制: 1024MB
原题链接

题目
给定一个正整数 X，正整数的 X 的约数的函数为 f(X)
给定一个正整数 N，求 F(1)x1 + F(2)x2 …. + F(N)xN

输入前提条件

  • 1 <=N <= 10000000

输出
输出 F(1)x1 + F(2)x2 …. + F(N)xN

例 1
输入

4

输出

23

f(1) = 1
f(2) = 2
f(3) = 2
f(4) = 3
所以最终的结果是
1×1 + 2×2 + 2×3 + 3×4 = 1 + 4 + 6 + 12 = 23

例 2
输入

100

输出

26879

例 3
输入

10000000

输出

838627288460105

注意溢出问题

读懂题目
从 1 到 N，每个数乘以这个数约数的个数，然后相加
N 最大可以达到 10 的 7 次方，所以，不能用 o(N*N) 的复杂度

解题思路

如图所示，我们以 N = 6 为例。
1 到 6 的每个数的约数都在下面的方块中显示
因为最终要求的是
f(1)x1 + f(2)x2 + f(3)x3 + f(4)x4 + f(5)x5 + f(6)x6

我们整体来考虑这个算式的话
蓝色方块下面的彩色小方块，存在的话，就会在最终的结果上贡献蓝色方块的数值
比如红色小方块 3，拥有 3 为约数的蓝色方块是 3，6
所以最终结果根据红色方块 3 的个数和所在地，加上 3 和 6


如图所示
拥有 1 为约数的数都加起来(1 + 2 + 3 + 4 + 5 + 6)


如图所示
拥有 2 为约数的数都加起来(2 + 4 + 6)


如图所示
拥有 3 为约数的数都加起来(3 + 6)


如图所示
拥有 4 为约数的数都加起来 (4)
拥有 5 为约数的数都加起来 (5)
拥有 6 为约数的数都加起来(6)

最后转换成从 1 到 N 的等差数列的求和
i 为 1 到 N 的遍历索引
fn(i) = i + 2i + 3i + 4i … + ni
n+i <= N
等差数列求和
sum(fn(i)) = ((i + (ni))) n /2

代码

N = int(input())

def calculate(n):
    result = 0
    for i in range(1, n + 1):
        num = n // i
        if num == 1:
            result += i
        else:
            start = i
            end = num * i
            total = ((start + end) * num) // 2
            result += total

    print(result)


calculate(N)

总结

这一题考察了等差数列的应用

※ 另外，我会在我的微信个人订阅号上推出一些文章，欢迎关注

退出移动版