UVA10229 Modular Fibonacci 【循环数列】

本文主要是介绍UVA10229 Modular Fibonacci 【循环数列】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

The Fibonacci numbers (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...) are defined by the recurrence:

    F0 = 0

    F1 = 1

    Fi = Fi−1 + Fi−2 for i > 1

Write a program which calculates Mn = Fn mod 2^m for given pair of n and m. 0 ≤ n ≤ 2147483647 and 0 ≤ m < 20. Note that a mod b gives the remainder when a is divided by b.

Input

Input consists of several lines specifying a pair of n and m.

Output

Output should be corresponding Mn, one per line.

Sample Input

11 7

11 6

Sample Output

89

25

问题链接：UVA10229 Modular Fibonacci

问题简述：（略）

问题分析：

  这是一个循环数列计算问题。

  这个问题也可以用矩阵快速幂进行计算。

程序说明：（略）

题记：（略）

参考链接：（略）

AC的C++语言程序如下：

/* UVA10229 Modular Fibonacci */#include <bits/stdc++.h>using namespace std;typedef long long LL;const int N = 1e6;
LL fib[N + 1];void setfib(LL mod, LL cycle)
{fib[0] = 1 % mod;fib[1] = 1 % mod;for(LL i=2; i<=cycle; i++)fib[i] = (fib[i - 2] + fib[i - 1]) % mod;
}int main()
{LL n, m;while(cin >> n >> m) {LL mod = 1LL << m;LL cycle = mod * 3 / 2;setfib(mod, cycle);cout << fib[--n % cycle] << endl;}return 0;
}

这篇关于UVA10229 Modular Fibonacci 【循环数列】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---