TopCoder

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

User's AC Ratio

85.7% (6/7)

Submission's AC Ratio

33.3% (11/33)

Tags

Description

小向拿到手的神秘道具的樣子就像是一個墜飾,本來看起來普普通通的。不過過了一會兒,墜飾便開始發出耀眼的光芒,朝著不知道哪個地方飄過去。要不是小向及時發現,墜飾早就自己飛走了。

「原來是這樣用的啊…」小向把墜飾戴了上去,而墜飾仍然朝著某個方向發出光芒,不斷地想往那個方向衝。看來那八成就是森林的正中心了。

獲得強大魔力且學會如何控制魔力的小向為了節省時間,試圖用飛的到森林中心。她從她剛感知到三個魔力源放出魔力,使自己漂浮。「好,成功了!」正當小向如此想時,她開始在空中四處亂撞,最後撞到了樹幹掉了下來。

「好痛喔…」小向摸摸自己的額頭,「可惡,再試一次!」

然而不管試了幾次,只有起步是穩的,過了一段時間之後她的飛行就會因為不明的原因開始不穩定,最後失控墜落。不過在失敗的經驗中,小向慢慢地發現到了要穩住飛行,她必須適當地調配三個魔力源所放出的魔力才不致於失去平衡。具體地說,假設三個魔力源放出的魔力值分別是正整數$x\leq y\leq z$,那麼她在高度是$\frac{1}{\frac{1}{x}+\frac{1}{y}+\frac{1}{z}}$時才會飛的最穩定。

「真是的…說不定又走的都比較快…」小向拍拍身上的灰塵。
「不過既然知道要怎麼飛了,接下來只剩下找出一個好的飛行方法了…」小向拿起身旁地樹枝,開始在地上寫下一行又一行的算式。

(這只是示意圖 千萬別覺得這圖對這題有幫助)
「還是得在某個高度穩定飛行…看起來還是先把在那高度飛行的所有可能的魔力調配方法找出來好了…」小向先得出了這個結論。
如果小向決定在高度$n$的地方飛行,她就得找到所有的三元正整數組$(x,y,z)$滿足$x\leq y\leq z$且$\frac{1}{n}=\frac{1}{x}+\frac{1}{y}+\frac{1}{z}$。

Input Format

每筆測資只包含一個正整數$n\leq 10^ 4$,代表小向決定穩定飛行的高度。

子任務(測資) 額外限制 分數
1 (0~2) $n\leq 3$ 8
2 (3~7) $n\leq 200$ 20
3 (8~12) $n\leq 1000$ 24
4 (13~17) 48

Output Format

請找出所有的$(x,y,z)$。為了方便,請將所有三元數組的$x,y$分別求和得到$X,Y$,再將兩數相加後輸出。

Sample Input

1

Sample Output

17

Hints

「太好了,終於算出來了!」小向放下木枝後馬上從三個魔力源放出魔力,終於順利地穩定飛行了。
依著墜飾的指示,小向往森林中央衝了過去。不過飛著飛著,小向突然覺得好像到了另一個空間似的。看來空間又被某人扭曲,接到了另一個時空去了。
一片的白光………

等小向回過神來,她發現她坐在辦公桌前。
小向不知為何成為了印尼巨港市的市長。

Problem Source

Problem Set / Description by Paupière

Subtasks

No. Testdata Range Score
1 0~2 8
2 3~7 20
3 8~12 24
4 13~17 48

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 1
3 1000 65536 262144 2
4 1000 65536 262144 2
5 1000 65536 262144 2
6 1000 65536 262144 2
7 1000 65536 262144 2
8 1000 65536 262144 3
9 1000 65536 262144 3
10 1000 65536 262144 3
11 1000 65536 262144 3
12 1000 65536 262144 3
13 1000 65536 262144 4
14 1000 65536 262144 4
15 1000 65536 262144 4
16 1000 65536 262144 4
17 1000 65536 262144 4