有效地添加可被3或5整除的数字

列出在给定数字下方为3或5的倍数的数字之和。

这是我的代码，找不到任何不必要的东西。 但hackerrank说它已经因超时而终止，时间限制是2秒，以给出预期的输出。 输入第一行包含’t’，表示测试用例的数量。 接下来是行，每行包含一个整数。

#include  void calc(int a){ int sum = 0; for(int a0=1; a0<a; a0++){ if(a0%3==0 || a0%5==0){ sum+=a0; } } printf("%d", sum); } int main(){ int t; scanf("%d",&t); int arr[t]; for(int a0 = 0; a0 < t; a0++){ scanf("%d",&arr[a0]); } for(int b=0; b<t; b++){ calc(arr[b]); printf("\n"); } return 0; } 

输入

 2 10 100 

输出必须是

 23 2318 

如果我们列出10以下的所有自然数是3或5的倍数，那么这些倍数的总和是23。

Answer 1

选项1

您试图在给定数字下将所有3或5的倍数相加。 你有没有尝试过如何在没有for循环的情况下做到这一点？ 我们试试吧。 嗯，“3或5”需要考虑很多。 让我们简化它，并尝试将99下的所有3的倍数相加：

3+6+9+12+15+...+99

你怎么能优化这个添加以避免for循环？ （在继续阅读之前这样做）

现在，如果你知道如何在给定的n下总和3的所有倍数，那么这是否能给你一个方法来对给定n下的所有3 或 5的倍数求和？ 嗯，序列3,6,9,12,15，…，n和5,10,15 ……之间的重叠是什么？ 也许如果你可以在n下加上3的倍数，并在n下加上5的倍数，那么你可以摆脱那个重叠 ？

选项2

好吧，假设我知道数字n下的3或5的倍数之和。 这有助于我在数字n + 1下找到3或5的倍数之和吗？ 也许我知道calc（n）在calc（n-1）方面是什么。 如果我能做到那么那将是伟大的，因为我可以保存 calc（n-1）而不是重新计算calc（n-1）。 要是…

Answer 2

以下是每个人的一些提示和链接：

• 低于a m = (a - 1) / k数可被k整除（具有整数除法）。
• 它们的总和是m * (m + 1) / 2 * k （通过高斯和公式 ，链接到德国维基 – 他们似乎更喜欢高斯）。

• 小于可被3或5整除的所有数字的总和与

   + the sum of all numbers smaller than `a` divisible by `3` + the sum of all numbers smaller than `a` divisible by `5` - the sum of all numbers smaller than `a` divisible by `15` 

  （通过包含 – 排除原则 ）

这为您提供了恒定时间算法：

 #include  /* sums the numbers smaller than `a` that are divisible by `k` */ int s(int a, int k) { int m = (a - 1) / k; return m * (m + 1) / 2 * k; } /* sums the numbers smaller than a that are divisible by both 3 and 5 */ int calc(int a) { return s(a, 3) + s(a, 5) - s(a, 15); } int main(){ int t; scanf("%d", &t); int arr[t]; for(int a0 = 0; a0 < t; a0++){ scanf("%d", &arr[a0]); } for(int b=0; b 

例：

 $ ./sumFizzBuzz 4 10 100 1000 10000 23 2318 233168 23331668 

对不起，这必须是，有太多的循环 - ＆ - 废话在这里和“几乎重复”的问题...

Answer 3

 #include  void calc_faster(int a) { int mid=0,sum=0; for(unsigned int i = a-1;i>0;i--) {if(i%3==0) { if(i%5==0) { mid=i; break; } else sum+=i; } else if(i%5==0) sum+=i; } sum+=mid*(7*mid+15)/30; printf("%d\n",sum); } int main() { unsigned int t; unsigned int temp; scanf("%d",&t); unsigned int arr[t]; for(register unsigned int a0 = 0; a0 < t; a0++) { scanf("%d",&arr[a0]); } for(register unsigned int b=0; b