超过时间和记忆限制- Python3 -数论
超过时间和记忆限制- Python3 -数论
提问于 2018-03-25 21:11:54
我试图找出所有数字的3或5的倍数之和，直到N。
这是一个关于HackerEarth的练习问题。我能够通过所有的测试用例，除了1。我得到一个时间和内存超过错误。我查阅了文档，了解到int可以处理大量数字，并且删除了bignum类型。
我仍然在学习python，并将感谢任何建设性的反馈。
请你指出正确的方向，这样我就可以自己优化代码了吗？
test_cases = int(input())
for i in range(test_cases):
user_input = int(input())
sum = 0
for j in range (0, user_input):
if j % 3 == 0:
sum = sum + j
elif j % 5 == 0:
sum = sum + j
print(sum)回答 1
Stack Overflow用户
发布于 2018-03-25 22:05:29
在这样的问题中，试着用一些数学来找到一个直接的解决方案，而不是强迫它。
你可以计算k小于n的倍数，并计算倍数之和。
例如，对于k=3和n=13，您有13 // 3=4个倍数。
这4个倍数之和为3*1 + 3*2 + 3*3 + 3*4 =3* (1+2+3+4)
然后，使用以下关系: 1+2+....+n = n*(n+1)/2
要将3和5的倍数之和，可以将3的倍数相加，加上5的倍数之和，再减去两次: 15的倍数。
所以，你可以这样做：
def sum_of_multiples_of(k, n):
"""
Returns the sum of the multiples of k under n
"""
# number of multiples of k between 1 and n
m = n // k
return k * m * (m+1) // 2
def sum_under(n):
return (sum_of_multiples_of(3, n)
+ sum_of_multiples_of(5, n)
- sum_of_multiples_of(15, n))
# 3+5+6+9+10 = 33
print(sum_under(10))
# 33
# 3+5+6+9+10+12+15+18 = 78
print(sum_under(19))
# 78页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/49480978
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号