切換
舊版
前往
大廳
主題

ZeroJudge - d264: 極值問題 解題心得

Not In My Back Yard | 2018-08-29 20:13:49 | 巴幣 0 | 人氣 102

題目連結:

題目大意:
給定K(1 ≦ K ≦ 10 ^ 9)。求滿足(N ^ 2-NM-M ^ 2)^ 2=1的數對中,N ^ 2+M ^ 2的值最大的那一對(N, M)。

解題思維:
題目的方程式,是一個有關於費波納契數列的恆等式(Identity)。任一組相鄰的費氏數列項次都會滿足該式,而也只有費氏數列會滿足此恆等式。

因此題目的所求即是小於等於K的,最接近的相鄰兩項費氏數列項的值。



至於關係式的來由,就讓我們回顧之前的文章出現過推算下一項費氏數列的矩陣,如下圖的左邊的陣列:

因為0和1剛好是費氏數列的第零項、第一項(或第二項)的值,因此我們可以發現此陣列如果自乘n次(n>0),會有以下關係:

接下來我們將此陣列稱為M,並將其當作行列式,得行列式值為-1。因此M ^ n的行列式值為(-1)^ n。(行列式的詳細資訊可以參照WIKI的條目

所以我們便得以下關係式:

根據費氏數列的定義展開n+1的那一項,並化簡關係式:

然後將等號兩邊平方,即獲得了我們這次題目的方程式。(事實上左式跟題目差一個負號,但是平方可以抵銷負號,所以等價)


此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作