【算法题】Multiples of 3 and 5总结

哈哈 阅读:410 2022-03-12 16:24:56 评论:0
本文章主要介绍了【算法题】Multiples of 3 and 5,具有不错的的参考价值,希望对您有所帮助,如解说有误或未考虑完全的地方,请您留言指出,谢谢!

Multiples of 3 and 5

原题

题意如下:

找出N以内的3和5的倍数的和。

思路

1、刚看到觉得好弱智,直接遍历一遍不就OK了吗?但是第2和第3个测试用例报了TLE,超时。

2、然后想不出来了,搜了一下,发现有一个类似的题计算1000以内的3和5的倍数的和,用的是算出3的倍数的和加上5的倍数的和减去15的倍数的和,因为是直接计算所以不需要遍历,自然就快了。按照同样的思路,可以找到小于N的最大的3的倍数,5的倍数和15的倍数。

代码

int main(){ 
    int t; 
    cin >> t; 
    for(int a0 = 0; a0 < t; a0++){ 
        int n; 
        cin >> n; 
        long sum = 0; 
        long p = (n-1)/3; 
        sum += (3+p*3) * p /2; 
        p = (n-1)/5; 
        sum += (5+p*5) * p / 2; 
        p = (n-1)/15; 
        sum -= (15+p*15) * p / 2; 
        cout<<sum<<endl; 
    } 
    return 0; 
} 

其中的sum和p必须为long类型,因为我开始用的int又给WA了,会超出int范围。

附上原题链接:IT虾米网


标签:加密算法
声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

我的关注

全民解析

搜索
排行榜
关注我们