SGU 105-DIV 3
Mean:
定义这样一种数列：1，12，123..
给出一个n，求这个数列中能被3整除的数的个数.
analyse:
这道题可以用分析的方法解决：
对于正整数k，k+1，k+2总有
k+(k+1)+(k+2)
=k+k+1+k+2
=3k+3
=3(k+1)
3(k+1)可以被3整除,而且，一个数是否能被3整除表现为它的各位数字之和能否被三整除.
这就意味着对于一个数12345678910111213...k(连写)，我们可以从后面开始，把数字三个一组划去，剩下三个或不足三个数为止，那么剩下的数对于3的整除情况和原数一致.
例如
123456789
划去一组 123456
划去一组 123
12可以被3整除，那么123456789也可以。又比如
1234567891011121314
划去一组 1234567891011
划去一组 12345678
划去一组 12345
划去一组 12
123可以被3整除，那么1234567891011121314也可以。再比如
1234
划去一组 1
1不能被3整除，1234也不能。
我们可以归一下类，对于一个由前k个正整数连写成的数m，如果k与3相除，余数是0或2(分别对应上述的第一和第二种情况)，那么m可以被3整除；如果余数是1，那么m不能被3整除。
综上题目可以转化为求出1-n之间有多少个能被3整除或被三整除余2的数，这就不难计算了。比较简便的方法是找出1-n之间被3除余数为1的数有多少个，记为x，那么n-x即为所求。
现在的主要矛盾是求出x，先观察前几个正整数：
1 2 3 4 5 6 7 8
^ ^ ^
其中被标记的数被3除，余数是1。可以发现，从1开始，需要统计的数在数列中出现的周期是3，而且这些数总是出现在每个周期的第一位，因此：对于一个长度为n的数列，它含有的周期的个数(n/3向上取整数)就是上文所提的x。
注意：由于这些数总是出现在每个周期的第一位，所以不满一周期(n被3除有余数)按照一完整周期进行计算。
Time complexity: O(1)
view code