Python3求N以内3或5的倍数之和遇超时及内存超限问题求助

嘿，我来帮你捋捋这个超时问题的优化思路！你遇到的Time and memory limit exceeded，大概率是因为用了逐个遍历判断是否为3或5倍数的暴力解法——这种方法在N特别大的时候（比如1e12这种量级），循环次数直接拉满，肯定会超时。

下面给你几个具体的优化方向，你可以自己动手调整代码：

1. 用数学公式替代循环（核心优化） #

这是解决这类问题的最优解，时间复杂度直接降到O(1)，不管N多大都能瞬间出结果。原理很简单：

• 3的倍数是等差数列：3,6,9,...,3k（k是N//3），求和用等差数列公式：3 * k*(k+1)//2
• 5的倍数同理：5 * m*(m+1)//2，其中m=N//5
• 注意！15是3和5的最小公倍数，会被重复计算两次，所以要减去15的倍数之和：15 * p*(p+1)//2，其中p=N//15
• 最终结果就是 sum3 + sum5 - sum15

2. 输入输出的高效处理 #

Python的标准输入输出如果处理不好，也会拖慢速度，尤其是测试用例很多的时候：

• 别用多次input()读测试用例，换成一次性读取所有输入（比如用sys.stdin.read()），再分割处理
• 输出时别多次print()，先把所有结果存到列表里，最后一次性用'\n'.join()输出

给你个简单的代码示例参考：

import sys

def get_sum(n):
    count3 = n // 3
    sum3 = 3 * count3 * (count3 + 1) // 2
    count5 = n // 5
    sum5 = 5 * count5 * (count5 + 1) // 2
    count15 = n // 15
    sum15 = 15 * count15 * (count15 + 1) // 2
    return sum3 + sum5 - sum15

def main():
    all_input = sys.stdin.read().split()
    test_num = int(all_input[0])
    results = []
    for i in range(1, test_num + 1):
        n = int(all_input[i])
        results.append(str(get_sum(n)))
    print('\n'.join(results))

if __name__ == "__main__":
    main()

3. 砍掉冗余计算 #

如果你之前的代码里有重复判断、多余的变量操作，直接删掉就行——毕竟用了数学公式后，那些循环里的判断逻辑都不需要了。

另外你提到的Python int处理大数的问题，完全不用担心，Python的int本身就支持任意精度，不会有溢出问题，这点不用纠结。

先试试把暴力循环改成数学公式的方法，应该就能通过那个超时的测试用例啦！如果还有问题，再检查下输入输出的处理是不是足够高效。

内容的提问来源于stack exchange，提问作者YYashwanth