TopCoder

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

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

66.7% (6/9)

Description

還記得TIOJ1185-三角蕃的煩惱嗎?

三角蕃又有煩惱了!

他打算在家裡旁邊設置一個花圃,

說到花圃當然就會想到籬笆,三角蕃也興奮的想要作一個漂亮的籬笆。

於是他到木材店買了一根 n 公尺長的木板,打算切割後作籬笆。

回到家裡之後,他突然不知道該如何切割,才能作成漂漂亮亮的籬笆。

他希望他的籬笆是三角形的,而且不能有任何凸出來的地方,三線段的頂點必須對著頂點。

而又因為美觀的關係,他希望每邊的邊長都是整數,這樣規畫起來比較輕鬆一些。

另外又因為節能減碳的關係,所以三角蕃不希望浪費掉任何一點木材。

但這實在是有太多種方法了,所以三角蕃想要知道究竟有多少種方法可以在切割後能成就漂亮的籬笆。

PS:因為視角的關係,所以(2,2,1)、(2,1,2)以及(1,2,2)視為不同的組合。

Input Format

本題有多組測試資料:

每筆測試資料只有一行一個正整數 n ,代表三角蕃買到的木材長度(n<=5*107)

Output Format

請對於每筆資料輸出一格數字 k ,代表對於長度 n 的木板,共有 k 種方式可以切割成完美的籬笆。

Sample Input

3
4
5

Sample Output

1
0
3

Hints

Problem Source

原TIOJ1467 / 建中校內培訓第四次模擬考試。
Problem Setter:hallogameboy、peter50216
(Adapt From:USACO 08' Oct)

Subtasks

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