uva 10229 Modular Fibonacci

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

原题：
The Fibonacci numbers (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …) are defined by the recurrence:
F 0 = 0
F 1 =1
F i = F i−1 + F i−2 for i > 1
Write a program which calculates M n = F n 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 M n , one per line.
Sample Input
11 7
11 6
Sample Output
89
25

中文：
让你计算fn mod 2^m次幂的结果，其中fn为斐波那契数列。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll pow2[21];
ll circle[21];
ll solve(ll n,ll m)
{n=n%circle[m];if(m==0||n==0)return 0;if(n==1)return 1;ll f1=0,f2=1,f3;for(int i=2;i<=n;i++){f3=(f1+f2)%pow2[m];f1=f2;f2=f3;} return f3;
}
int main()
{ios::sync_with_stdio(false);pow2[0]=1;circle[0]=1;for(int i=1;i<20;i++)pow2[i]=pow2[i-1]*2;for(int i=1;i<20;i++){ll f1=0,f2=1,f3;int j;for(j=1;;j++){f3=(f1%pow2[i]+f2%pow2[i])%pow2[i];if(f3==1&&f2==0)break;f1=f2;f2=f3;}circle[i]=j;}int n,m;while(cin>>n>>m){//    cout<<circle[m]<<endl;cout<<solve(n,m)<<endl;}return 0;
}

思路：

找循环节，保存下来即可。

这篇关于uva 10229 Modular Fibonacci的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---