[Java] 蓝桥杯PREV-29 历届试题 斐波那契

问题描述

斐波那契数列大家都非常熟悉。它的定义是：

f(x) = 1 …. (x=1,2)

f(x) = f(x-1) + f(x-2) …. (x>2)

对于给定的整数 n 和 m，我们希望求出：

f(1) + f(2) + … + f(n) 的值。但这个值可能非常大，所以我们把它对 f(m) 取模。

公式如下

但这个数字依然很大，所以需要再对 p 求模。

输入格式

输入为一行用空格分开的整数 n m p (0<n, m, p<10^18)

输出格式

输出为1个整数，表示答案

样例输入

2 3 5

样例输出

0

样例输入

15 11 29

样例输出

25

package prev29;
 
import java.math.BigInteger;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long n = in.nextLong();
        long m = in.nextLong();
        BigInteger p = in.nextBigInteger();
        in.close();
 
        BigInteger f1 = new BigInteger("1");
        BigInteger f2 = new BigInteger("1");
        BigInteger fm = new BigInteger("1");
        for (long i = 3; i <= m; i++) {
            fm = f1.add(f2);
            f1 = f2;
            f2 = fm;
        }
 
        f1 = new BigInteger("1");
        f2 = new BigInteger("1");
        BigInteger sum = new BigInteger("2");
        BigInteger fn = new BigInteger("0");
        for (long i = 3; i <= n; i++) {
            fn = f1.add(f2);
            sum = sum.add(fn);
            f1 = f2;
            f2 = fn;
        }
 
        System.out.println(sum.mod(fm).mod(p));
    }
 
}