在你算完病毒個數模 3 的餘數之後(看這裡),這飛行船繼續在空中徘徊。恐怖分子並沒有要妥協的意思,而為了不讓病毒擴散至地面,這艘飛船不能降落。
從病毒開始擴散,已經過了$i$分鐘。飛船上已經只剩你一個人了(其它人已因致命的肺噬病毒而死亡,然而你身上帶有某種神奇的抗體,可能是你算出了病毒個數模3的緣故吧)。盡責的船長在斷氣前的那剎那開啟了自動飛航模式,讓飛船得以繼續在空中徘徊。
這時,從你背後傳來急促的腳步聲。當你心想著「原來還有倖存者啊」回頭看時,你發現恐怖份子的同夥正拿著棒子朝著你的頭一揮………
等你醒來的時候,你發現你被拷起來,手腳無法動彈了。你抬頭看了一下時鐘,「啊…從病毒開始擴散已經過了 $j$ 分鐘啊…」
這時恐怖份子拿著槍指著你的頭:「你是怎麼弄到解藥的?快說!只要解藥存在,我輩(?)征服世界的野望就…」
在這大難臨頭的當下,你唯一想做的事情是……
計算 $F_i$ 和 $F_j$ 的最大公因數!
註:注意
(1) $F_1=1, F_2=2$
(2) $F_{n+2}=F_{n}+F_{n+1}\quad\forall n\in\mathbb{N}$(意思是「對於所有正整數 $n$」。)
輸入只有一行,含有兩個正整數$i,j\leq 10^ {18}$。
為了維持故事中$i$和$j$的先後順序,$i<j$。
子任務(測資) | 額外限制 | 分數 |
1 (0~4) | $i< j\leq 80$ | 3 |
2 (5~9) | $i< j\leq 10^ 3$ | 12 |
3 (10~14) | $i< j\leq 10^ 6$ | 37 |
4 (15~19) | 無限制 | 48 |
請輸出一個數,代表$F_i$和$F_j$的最大公因數。因為答案有點大,請模$10^ 9+7$後再輸出。
$F_5=8, F_8=34$
兩數的最大公因數是2
Problem set / Description by Paupière
建國中學105學年度校內第一次模擬賽pF
No. | Testdata Range | Score |
---|---|---|
1 | 0~4 | 3 |
2 | 5~9 | 12 |
3 | 10~14 | 37 |
4 | 15~19 | 48 |