數論 - SGU 105 DIV3SGU 105-DIV 3 Problem's Link

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

/**

* -----------------------------------------------------------------

* Copyright (c) 2016 crazyacking.All rights reserved.

*       Author: crazyacking

*       Date  : 2016-01-06-17.53

*/

#include <queue>

#include <cstdio>

#include <set>

#include <string>

#include <stack>

#include <cmath>

#include <climits>

#include <map>

#include <cstdlib>

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

using namespace std;

typedef long long(LL);

typedef unsigned long long(ULL);

const double eps(1e-8);

int main()

{

   int n = 0;

   scanf("%d", &n);

   if(n % 3 == 0)

   {

       printf("%d", n/3*2);

   }

   else

       printf("%d", n/3*2+n%3-1);

   return 0;

}