燈怪被關在阿拉丁神燈裡已經好幾十萬年了,這使得燈怪的脾氣變得有點奇怪。他不再對所有釋放他離開神燈的人都一視同仁地給三個願望,反而要求得到願望前必須正確回答他所問的問題,如果回答不出來,就要代替燈怪被關在神燈裡。他的問題是一個數列問題,題目如下:
數列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個最簡分數為何?請寫一個方程式回答燈怪的問題。
輸入檔第一行有一個正整數n,n最少為2,最多為70。
請由螢幕印出兩行資料,說明如下:
1. 第一行列出數列共有幾個最簡分數。
2. 第二行列出倒數第n個最簡分數,如果最簡分數個數小於n,則請列出最大數字(即第一個最簡分數)。
原TIOJ1234 / TOI2006初選(prob 2)。
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 |