【算法题】Multiples of 3 and 5

2024-08-24 07:29:04

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范围。

附上原题链接：https://www.hackerrank.com/contests/projecteuler/challenges/euler001/submissions/code/7962817

最新文章

热门文章