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

微信扫一扫,分享到朋友圈

[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));
    }
 
}

❤❤点击这里 -> 订阅PAT、蓝桥杯、GPLT天梯赛、LeetCode题解离线版❤❤

微信扫一扫,分享到朋友圈

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

[Java] 蓝桥杯PREV-33 历届试题 兰顿蚂蚁

上一篇

Some questions I find interesting

下一篇

你也可能喜欢

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

长按储存图像,分享给朋友