java实现第五届蓝桥杯斐波那契

斐波那契

标题：斐波那契

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

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) 取模。

公式参见【图1.png】

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

【数据格式】

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

输出为1个整数

例如，如果输入：

3 5

程序应该输出：

再例如，输入：

11 29

程序应该输出：

资源约定：

峰值内存消耗（含虚拟机） < 256M

CPU消耗 < 2000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。

注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。

注意：主类的名字必须是：Main，否则按无效代码处理。

首先，关于斐波那契数的求取，如果使用递归法求取，会出现远远超时；迭代法求取差不多也会超时，此处，最好使用矩阵相乘法求取第n个斐波那契数。

其次，关于求取前n个斐波那契数和的问题，利用斐波那契数的性质（网上资料参考所得）:S(n) = F(n+2) - 1，其中S(n)是前n个斐波那契数的和，F(n + 2)是第n+2个斐波那契数。

最后，要考虑n，m的取值问题，经过使用计算机运算检测，一般n > 100，F(n)就会超过long型最大值，所以此处建议使用BigInteger类型，来存储斐波那契数。

下面的代码仅供参考，不保证n、m、p达到10^18数量级时，大整数类型的取余不会出现内存溢出问题哦。

import java.math.BigInteger;

import java.util.Scanner;

public class Main {

    public static BigInteger[][] ONE = {{BigInteger.ONE, BigInteger.ONE},

        {BigInteger.ONE,BigInteger.ZERO}};

    public static BigInteger[][] ZERO = {{BigInteger.ZERO,BigInteger.ZERO},

        {BigInteger.ZERO,BigInteger.ZERO}};

    //求取矩阵ONE的n次方

    public BigInteger[][] getOneOfN(long n) {

        if(n == 0)

            return ZERO;

        if(n == 1)

            return ONE;

        if((n & 1) == 0) {   //当n为偶数时

            BigInteger[][] A = getOneOfN(n >> 1);

            return multiMatrix(A, A);

        }

        //当n为奇数时

        BigInteger[][] A = getOneOfN(n >> 1);

        return multiMatrix(multiMatrix(A, A), ONE);

    }

    //求取矩阵A*B的值

    public BigInteger[][] multiMatrix(BigInteger[][] A, BigInteger[][] B) {

        BigInteger[][] result = new BigInteger[A.length][B[0].length];

        for(int i = 0;i < A.length;i++)

            for(int j = 0;j < B[0].length;j++)

                result[i][j] = BigInteger.ZERO;

        for(int i = 0;i < A.length;i++)

            for(int j = 0;j < B.length;j++)

                for(int k = 0;k < A[0].length;k++)

                    result[i][j] = result[i][j].add(A[i][k].multiply(B[k][j]));

        return result;

    }

    //获取第n个斐波那契数

    public BigInteger getFibonacci(long n) {

        if(n == 1 || n == 2)

            return BigInteger.ONE;

        BigInteger[][] A  = new BigInteger[1][2];

        A[0][0] = BigInteger.ONE;

        A[0][1] = BigInteger.ONE;

        BigInteger[][] B = getOneOfN(n - 2);

        A = multiMatrix(A, B);

        return A[0][0];

    }

    public static void main(String[] args) {

        Main test = new Main();

        Scanner in = new Scanner(System.in);

        long n = in.nextLong();

        long m = in.nextLong();

        BigInteger p = in.nextBigInteger();

        BigInteger result = BigInteger.ZERO;

        result = test.getFibonacci(n + 2).subtract(BigInteger.ONE);

        result = result.mod(test.getFibonacci(m));

        result = result.mod(p);

        System.out.println(result);

    }

}