TopCoder

User's AC Ratio

99.0% (101/102)

Submission's AC Ratio

65.3% (113/173)

Tags

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 1

4

Sample Output 1

5
2/3

Sample Input 2

5

Sample Output 2

9
1/2

Hints

Problem Source

原TIOJ1234 / TOI2006初選(prob 2)。

Subtasks

No. Testdata Range Score
1 0 14
2 1 14
3 2 14
4 3 14
5 4 14
6 5 14
7 6 16

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 65536 262144 1
1 5000 65536 262144 2
2 5000 65536 262144 3
3 5000 65536 262144 4
4 5000 65536 262144 5
5 5000 65536 262144 6
6 5000 65536 262144 7