本文主要是介绍Elegant fibonacci numbers again，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Problem Description
Fibonacci numbers are nice simple integers. All of you are familiar with it, aren’t you?
The Fibonacci sequence <F[n]> are defined by the recurrence:
F[0]=0;
F[1]=1;
F[n]=F[n-1]+F[n-2], for n>1
You know that the value of F[n] increases rapidly when the n becomes larger. So for each test case,output the value F[n] mod m will be ok.
The Fibonacci sequence <F[n]> are defined by the recurrence:
F[0]=0;
F[1]=1;
F[n]=F[n-1]+F[n-2], for n>1
You know that the value of F[n] increases rapidly when the n becomes larger. So for each test case,output the value F[n] mod m will be ok.
Input
The first line of the input is a positive integer.It is the number of the test cases followed. Each test case contains two integers n (0<=n<2^32) and m (0<m<10000). There may be one or several spaces between the two integers.
Output
The output of the program should consist of one line of output for each test case.The output of each test case only contains one integer which equals to the value F[n] mod m. No any redundant spaces are needed.
Sample Input
2 1 1000 2 100
Sample Output
1 1
// 关键字: 斐波拉契数列的矩阵求法
//标程：
#include<stdio.h>
struct ss
{
int a[2][2];
};
ss fun(ss x,ss y,__int64 m)
{
ss ret;
ret.a[0][0]=(x.a[0][0]*y.a[0][0]%m+x.a[0][1]*y.a[1][0]%m)%m;
ret.a[0][1]=(x.a[0][0]*y.a[0][1]%m+x.a[0][1]*y.a[1][1]%m)%m;
ret.a[1][0]=(x.a[1][0]*y.a[0][0]%m+x.a[1][1]*y.a[1][0]%m)%m;
ret.a[1][1]=(x.a[1][0]*y.a[0][1]%m+x.a[1][1]*y.a[1][1]%m)%m;
return ret;
}
ss f(ss ans,__int64 n,__int64 m)
{
ss ret,temp;
if(n==0)
{
ret.a[0][0]=1, ret.a[0][1]=0;
ret.a[1][0]=0, ret.a[1][1]=1;
return ret;
}
if(n==1) return ans;
temp=f(ans,n/2,m);
ret=fun(temp,temp,m);
if(n%2==1) ret=fun(ret,ans,m);
return ret;
}
int main()
{
//freopen("a.txt","r",stdin);
__int64 n,m;
int t,i;
scanf("%d",&t);
while(t--)
{
scanf("%I64d%I64d",&n,&m);
if(n==0) { printf("0\n"); continue;}
ss ans;
ans.a[0][0]=1, ans.a[0][1]=1;
ans.a[1][0]=1, ans.a[1][1]=0;
ss s=f(ans,n-1,m);
printf("%d\n",s.a[0][0]);
}
return 0;
}
这篇关于Elegant fibonacci numbers again的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
