TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

66.7% (6/9)

Submission's AC Ratio

45.5% (10/22)

Description

『幸運數』是在1955年波蘭數學家烏拉姆提出,它其實是一串藉由特定規則而得的正整數數列。要如何得到一串幸運數列呢?
我們先列出正整數數列:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25...
接著刪去所有的偶數,剩下奇數數列:
1 3 5 7 9 11 13 15 17 19 21 23 25...
數列的第2個數為3,故從頭開始3個一數將數字刪去:
1 3 7 9 13 15 19 21 25...
數列的第3個數為7,故從頭開始7個一數將數字刪去:
1 3 7 9 13 15 21 25...
重複以上的過程,最後留下來的數字便形成幸運數列:
1 3 7 9 13 15 21 25 31 33 37 43 49 51 63 67 69 73 75 79 87 93 99 ...
皮皮最近正不斷累積TIOJ的Accepted,因為皮皮對解題極度有把握,他絕不會有卡關的問題。
經過一段時間,他發現他預定要寫到的題數—193,竟然也是幸運數(數列第38個)!於是他對幸運數便有了極大的好奇心,希望Lucky Number可以帶給他極大的破題功力。不過皮皮對第N個數是哪個幸運數的問法毫無興趣,此刻他最想知道的是:輸入一個數字N,請問1到N之間存在多少個幸運數?

Input Format

輸入可能包含多筆測試資料。
每筆測試資料有一個正整數N(1 ≦ N ≦ 1000000)。
當N = 0時,代表輸入結束,聰明的你當然不會對它輸出任何資料。

Output Format

請輸出一個整數,表示1到N間有多少個幸運數。

Sample Input

1
5
24
25
0

Sample Output

1
2
7
8

Hints

(皮皮補註:這題絕對不是我出的= =)

Problem Source

原TIOJ1251 / INFOR 21st幹部考(prob G)。Problem Setter:peter50216。

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
5 1000 65536 262144 6
6 1000 65536 262144 7
7 1000 65536 262144 8
8 1000 65536 262144 9
9 1000 65536 262144 10