挑战3

rosynirvana

首先是平庸解法

这个和会不会溢出？我不知道，但是明显在int64下不会溢出（1到123456的和都不会溢出，更别说其中的一部分了），所以用long long int来存放和总是没问题的
（注意，mingw下面printf的占位符是非标准的%I64d，但是这个问题下不会溢出，所以没问题）

如何表达7的倍数和末尾是7的数？ i % 7 == 0 || i % 10 == 7，只要满足两者之一就加起来，不会有重复计算的问题

1. #include <stdio.h>
   
2. 
   
3. int main()
   
4. {
   
5.   long long int sum = 0;
   
6.   int i;
   
7.   for(i = 1; i < 123456; ++i)
   
8.     if(i % 7 == 0 || i % 10 == 7)
   
9.       sum += i;
   
10.   printf("%lld\n", sum);
    
11.   return 0;
    
12. }

复制代码

但是这样明显不是最好的解法，要扫描123456个数，并且做很多除法运算，稍微想一下就能降低一个数量级的运算量

7的倍数，从7开始每次加7就可以了，完全不用除法。末尾是7的数字也很简单，从7开始每次加10.
但是这样子会有重复计算的问题，所以在其中之一累加的时候，将重复的数字除去。
这样子只用扫描两万多个数字就可以了，而且除法只用做12345次。

1. #include <stdio.h>
   
2. 
   
3. int main()
   
4. {
   
5.   long long int sum = 0;
   
6.   int i;
   
7.   for(i = 7; i < 123456; i += 7)
   
8.     sum += i;
   
9.   for(i = 7; i < 123456; i += 10)
   
10.     if(i % 7 != 0)
    
11.       sum += 1;
    
12.   printf("%lld\n", sum);
    
13.   return 0;
    
14. }

复制代码

这样是最好的解法吗？仍然不是，请注意， 所谓7的倍数， 末尾是7的数，以及同时满足两条件的数字，分别构成等差数列：
7, 14, 21, ....
7, 17, 27, ....
7, 77, 147, ...
所以只要求出这三个数列中小于123456的最大值，然后再用首项加尾项乘以项数除以2就可以了，完全不用线性扫描。
但是我不会去这么做，为什么？因为求一个等差数列小于x的最大值要解二次方程，并且涉及到取整数的问题，编程明显比上面第二段代码要复杂。这个数字很小，计算机实际运算的时间可以忽略，所以解决问题的差异就在编程时间上了。

所以，当你遇到这类问题时，应该优先尝试第一种方法，如果效果不理想就换第二种，实在不行再第三种换试试