hdu 4549 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]的值吗?

思路:观察发现。。。F[n] = a^(fib(n-1)) * b ^ (fib(n))

此处要用到指数循环节的知识:

111qqz_指数循环节学习笔记

a^n ≡ a^(n % Phi(M) + Phi(M)) (mod M) (n >= Phi(M))

然后 因为1000000007是质数,对于任意的x,有gcd(x,1000000007) = 1,所以可以结合费马小定理化简上式:

a^n ≡ a^(n%(m-1)) * a^(m-1)≡ a^(n%(m-1)) (mod m)

记得特判一下n为0和1的情况。

xiaodingli

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz