首页 > 代码库 > HDU4549 M斐波那契数列
HDU4549 M斐波那契数列
M斐波那契数列
题目分析:
M斐波那契数列F[n]是一种整数数列,它的定义如下:
F[0] = a
F[1] = b
F[n] = F[n-1] * F[n-2] ( n > 1 )
现在给出a, b, n,你能求出F[n]的值吗?
算法分析:
经过前面几项的推导,你会发现其中a,b的个数为斐波那契数相同。而我们知道斐波那契数是到20项后就会很大,所以要处理。而我们根据欧拉定理(费马小定理)可知道
A^(P-1)同余 1 模C,这题的C是质数,而且A,C是互质的。
所以直接A^(B%(C-1)) %C = A^B % C
比较一般的结论是 A^B %C = A^( B%phi(C)+phi(C) ) %C B>=phi(C)
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> using namespace std; typedef long long LL; const int MOD = 1000000007; struct Matrix{ LL mat[2][2]; LL row,col; Matrix(){}; Matrix(LL _r,LL _c):row(_r),col(_c){}; }; Matrix I(2,2),P(2,2); void Init(){ P.mat[0][0] = 0; P.mat[0][1] = P.mat[1][0] = P.mat[1][1] = 1; I.mat[0][0] = I.mat[1][1] = 1; I.mat[0][1] = I.mat[1][0] = 0; } //矩阵相乘 Matrix mul(Matrix A,Matrix B,LL mod){ Matrix C(2,2); memset(C.mat,0,sizeof(C.mat)); for(int i = 0;i < A.row;++i){ for(int k = 0;k < B.row;++k){ for(int j = 0;j < B.col;++j){ C.mat[i][j] = (C.mat[i][j] + A.mat[i][k] * B.mat[k][j] % mod) % mod; } } } return C; } //fib[n] % (c - 1) Matrix powmod(Matrix A,LL n,LL mod){ Matrix B = I; while(n > 0){ if(n & 1) B = mul(B,A,mod); A = mul(A,A,mod); n >>= 1; } return B; } //a ^ b % c LL powmod(LL a,LL n,LL mod){ LL res = 1; while(n > 0){ if(n & 1) res = (res * a) % mod; a = a * a % mod; n >>= 1; } return res; } int main() { Init(); LL a,b,n; while(~scanf("%I64d%I64d%I64d",&a,&b,&n)){ Matrix A = powmod(P,n,MOD - 1); //fib[n] % (mod -1 ) printf("%I64d\n",powmod(a,A.mat[0][0],MOD) * powmod(b,A.mat[1][0],MOD) % MOD); } return 0; }
HDU4549 M斐波那契数列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。