B - Lucas Number
Editorial
/


Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 200 点
問題文
今、日本は 11 月 18 日ですが、11 と 18 は隣り合うリュカ数です。
整数 N が与えられるので、N 番目のリュカ数を求めてください。
ただし、リュカ数は i 番目のリュカ数を L_i とすると、
- L_0=2
- L_1=1
- L_i=L_{i-1}+L_{i-2} (i≧2)
と定義される数とします。
制約
- 1≦N≦86
- 答えは 10^{18} より小さいことが保証される
- 入力は整数からなる
入力
入力は以下の形式で標準入力から与えられる。
N
出力
N 番目のリュカ数を出力せよ。
入力例 1
5
出力例 1
11
- L_0=2
- L_1=1
- L_2=L_0+L_1=3
- L_3=L_1+L_2=4
- L_4=L_2+L_3=7
- L_5=L_3+L_4=11
より、5 番目のリュカ数は 11 です。
入力例 2
86
出力例 2
939587134549734843
Score : 200 points
Problem Statement
It is November 18 now in Japan. By the way, 11 and 18 are adjacent Lucas numbers.
You are given an integer N. Find the N-th Lucas number.
Here, the i-th Lucas number L_i is defined as follows:
- L_0=2
- L_1=1
- L_i=L_{i-1}+L_{i-2} (i≥2)
Constraints
- 1≤N≤86
- It is guaranteed that the answer is less than 10^{18}.
- N is an integer.
Input
Input is given from Standard Input in the following format:
N
Output
Print the N-th Lucas number.
Sample Input 1
5
Sample Output 1
11
- L_0=2
- L_1=1
- L_2=L_0+L_1=3
- L_3=L_1+L_2=4
- L_4=L_2+L_3=7
- L_5=L_3+L_4=11
Thus, the 5-th Lucas number is 11.
Sample Input 2
86
Sample Output 2
939587134549734843