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

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144
1 1000 65536 262144
2 1000 65536 262144
3 1000 65536 262144
4 1000 65536 262144
5 1000 65536 262144
6 1000 65536 262144
7 1000 65536 262144
8 1000 65536 262144
9 1000 65536 262144