HDU 4549 M斐波那契数列
M斐波那契数列
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 5790 Accepted Submission(s): 1801
Problem Description
M斐波那契数列F[n]是一种整数数列，它的定义如下：
F[0] = a
F[1] = b
F[n] = F[n-1] * F[n-2] ( n > 1 )
现在给出a, b, n，你能求出F[n]的值吗？
Input
输入包含多组测试数据；
每组数据占一行，包含3个整数a, b, n（ 0 <= a, b, n <= 10^9 ）
Output
对每组测试数据请输出一个整数F[n]，由于F[n]可能很大，你只需输出F[n]对1000000007取模后的值即可，每组数据输出一行。
Sample Input
0 1 0
6 10 2
Sample Output
0
60
//思路：
// F[0]=a ;
// F[1]=b;
// F[2] = ab;
// F[3]= ab^2;
// F[4]= a^2*b^3;
// F[n]= a^( f[n-2] + f[n-3] ) * b^( f[n-1] + f[n-2] ) （ f[n]为斐波那契数列）
// 也就是F[n] = a^( f[n-1] ) * b^( f[n] ) ----------->> （ f[n]为斐波那契数列）
// 问题在于求出f[n] ,普通方法，肯定超时，要用到矩阵 快速幂
F[0] = a
F[1] = b
F[n] = F[n-1] * F[n-2] ( n > 1 )
变换公式：
进一步，可以得出直接推导公式：
还有要应用到，费马小定理 可用于简化 计算a^b( mod p )
费马小定理 :假如p是素数，且(a,p)=1那么a^(p-1) ≡1(mod p)
对于素数p，任取跟他互素的数 a，有a^(p-1)(mod p)=1
所以任取b，有 a^b%p= a^(b%(p-1))(%p)从而简化运算。
怎样理解呢？可以把b拆分成 k*（p-1）+r的形式
即a^( k*(p-1)+r) %p== a^(b%(p-1))(%p)
#include<iostream>
using namespace std;
#define ll long long int
ll A[2][2],ans[2][2];
const ll mod = 1000000007;
void set(ll a[][2],ll b[][2]){
for( int i=0;i<=1;i++)
for( int j=0;j<=1;j++)
a[i][j] = b[i][j];
}
void init( ll a[][2] , int op){
if( op == 0){
for( int i=0;i<=1;i++)
for( int j=0;j<=1;j++)
a[i][j]=0;
}
else if( op==1 ){
for( int i=0;i<=1;i++)
for( int j=0;j<=1;j++)
if( i==j )
a[i][j] = 1;
else a[i][j] = 0;
}
}
void Matrix( int b ){
ll tmp[2][2];
init(ans,1);
while( b ){
if( b&1){
set(tmp,ans);
init(ans,0);
for( int i=0;i<=1;i++)
for( int j=0;j<=1;j++)
for( int k=0;k<=1;k++)
ans[i][j] = (ans[i][j] + A[i][k]*tmp[k][j] )%( mod -1);
}
set(tmp,A);
init(A,0);
for( int i=0;i<=1;i++)
for( int j=0;j<=1;j++)
for( int k=0;k<=1;k++)
A[i][j] = ( A[i][j] + tmp[i][k] * tmp[k][j] ) %( mod-1) ;
b>>=1;
}
}
ll q_pow( ll a ,ll b ){
ll res =1 ;
while( b ){
if( b&1)
res = ( res * a ) % mod;
a = (a*a)%mod;
b>>=1;
}
return res;
}
int main(void){
long long a,b,n;
while( scanf("%lld%lld%lld",&a,&b,&n)!=EOF){
A[0][0] = 1;
A[0][1] = 1;
A[1][0] = 1;
A[1][1] = 0;
if( n==0 ){
printf("%lldn",a%mod);
continue;
}
else if( n==1 ){
printf("%lldn",b%mod);
continue;
}
Matrix( n-1 );
a = q_pow(a, ans[1][0] );
b = q_pow(b, ans[0][0] );
ll anss = (a*b)%mod;
printf("%lldn",anss);
}
return 0;
}
相关知识
斐波那契数列
关于斐波那契数列……设{fn}是斐波那契数列,则F1=F2=1,Fn=Fn
大自然里的斐波那契数列
斐波那契数列的各种求法（终于找全了！）
植物也懂数学？神奇的斐波那契数列
01串（类似于斐波那契数列）
斐波那契之花
【数学文化】数学之美：花朵中的斐波那契数列
斐波那契花菜，植物也有数学秘密？
斐波那契是中世纪最伟大的西方数学家
网址: HDU 4549 M斐波那契数列 https://m.huajiangbk.com/newsview854813.html
| 上一篇: 插花活动总结9篇 |
下一篇: 投票活动总结范文.doc |
