共计 938 个字符,预计需要花费 3 分钟才能阅读完成。
本文章为原创文章,未经过允许不得转载
运行要求
运行时间限制: 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)
总结
这一题考察了等差数列的应用
※ 另外,我会在我的微信个人订阅号上推出一些文章,欢迎关注