TopCoder

User's AC Ratio

97.8% (45/46)

Submission's AC Ratio

72.7% (48/66)

Description

燈怪被關在阿拉丁神燈裡已經好幾十萬年了,這使得燈怪的脾氣變得有點奇怪。他不再對所有釋放他離開神燈的人都一視同仁地給三個願望,反而要求得到願望前必須正確回答他所問的問題,如果回答不出來,就要代替燈怪被關在神燈裡。他的問題是一個數列問題,題目如下:

數列A(n)為一組最簡分數所形成的數列,這些最簡分數的值都大於0小於1,且分母小於等於n,同時數列中的數值依由大到小的方式排序之。例如:

A(3) = 2/3, 1/2, 1/3
A(4) = 3/4, 2/3, 1/2, 1/3, 1/4
A(5) = 4/5, 3/4, 2/3, 3/5, 1/2, 2/5, 1/3, 1/4, 1/5

燈怪要問的問題是這個數列是由幾個最簡分數所組成的?數列中倒數第n個最簡分數為何?請寫一個方程式回答燈怪的問題。

Input Format

輸入檔第一行有一個正整數n,n最少為2,最多為70。

Output Format

請由螢幕印出兩行資料,說明如下:
1. 第一行列出數列共有幾個最簡分數。
2. 第二行列出倒數第n個最簡分數,如果最簡分數個數小於n,則請列出最大數字(即第一個最簡分數)。

Sample Input

Sample Input #1:

4

Sample Input #2:

5

Sample Output

Sample Output #1:

5
2/3

Sample Output #2:

9
1/2

Hints

Problem Source

原TIOJ1234 / TOI2006初選(prob 2)。

Subtasks

For Testdata: 0 ~ 0, Score: 14
For Testdata: 1 ~ 1, Score: 14
For Testdata: 2 ~ 2, Score: 14
For Testdata: 3 ~ 3, Score: 14
For Testdata: 4 ~ 4, Score: 14
For Testdata: 5 ~ 5, Score: 14
For Testdata: 6 ~ 6, Score: 16
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 5000 65536 262144
1 5000 65536 262144
2 5000 65536 262144
3 5000 65536 262144
4 5000 65536 262144
5 5000 65536 262144
6 5000 65536 262144