[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 历届试题 斐波那契

原文 

https://www.liuchuo.net/archives/7112

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » [Java] 蓝桥杯PREV-29 历届试题 斐波那契

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址