主題

ZeroJudge - d639: 企鵝村三兄弟penguin 解題心得

Not In My Back Yard | 2021-09-04 00:00:03 | 巴幣 0 | 人氣 68

題目連結:


題目大意:
現有一數列:第 1 、 2 、 3 項皆是 1。第 i 項(i > 3)開始為其前三項之和,因此第 4 項為 3 、第 5 項為 5 、第 6 項為 9……以此類推。

輸入給定一正整數 n(1 ≦ n ≦ 2147483647),試問此數列第 n 項之值為何?請將答案模 10007 後輸出。



範例輸入:
8


範例輸出:
31


解題思維:
基本就是這題 n = 3 時的情況,即費氏數列的推廣版本。

而這個數列也有著屬於它的、類似費氏數列的皮薩諾週期(Pisano Period
),可以參見這題因此也先求出此數列模 10007 的週期(應為每 2781668 項循環一次,有錯請指正),然後便可以將 n 變小至 ≦ 2781668 的等價項接著求得該項之值即可。

上述兩個作法都是可行的。




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

創作回應

相關創作

更多創作